\input cwebmac
\documentstyle[comments,a4,psfig]{cweb}

\input{/KM/usr/schirra/styles/transfig}

\voffset=-0.5cm
\textwidth		14cm
\oddsidemargin          0.4cm
\evensidemargin         1.4cm
\marginparwidth		1.9cm
\marginparsep		0.4cm
\marginparpush		0.4cm
\topmargin		0cm
\headsep		1.5cm
\textheight		21.5cm
\footskip		2.2cm



\begin{document}



\thispagestyle{empty}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

        \title{An Implementation of the\\
 Hopcroft and Tarjan\\
 Planarity Test and Embedding Algorithm}\thanks{This work was supported in part
by the German Minis
try for Research and Technology (Bundesministerium f\"ur Forschung und
Technologie) under grant ITS
 9103 and by the ESPRIT Basic Research Actions Program under contract No. 7141
(project ALCOM II).}

\author{Kurt Mehlhorn\\
        {\footnotesize  Max-Planck-Institut f\"ur Informatik,}\\[-0.7ex]
   	{\footnotesize 66123 Saarbr\"ucken, Germany}\\[0.7ex]
	\and Petra Mutzel\\
        {\footnotesize  Institut f\"ur Informatik,}\\[-0.7ex]
	{footnotesize Universit\"at zu K\"oln, 50969 K\"oln}\\[0.7ex]
	\and Stefan N\"aher\\
        {\footnotesize  Max-Planck-Institut f\"ur Informatik,}\\[-0.7ex]
   	{\footnotesize 66123 Saarbr\"ucken, Germany}\\[0.7ex]}


        \date{}
        \maketitle


\setcounter{page}{0}
\thispagestyle{empty}

%%%%%%% Abstract %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vspace*{2.2cm}

\begin{abstract}
We describe an implementation of the Hopcroft and Tarjan planarity test and
embedding algorithm. The program tests the planarity of the input
graph and either constructs a combinatorial embedding (if the graph
is planar) or exhibits a Kuratowski subgraph (if the graph is non-planar).

\end{abstract}

\tableofcontents


\N{1}{1}Introduction.

We descibe two procedures to test the planarity of a graph \PB{\|G}:

\begin{center}
\PB{\&{bool} \\{planar}(\&{graph} ${}{\AND}\|G,{}$\&{bool} \\{embed}${}\K%
\\{false})$}
\end{center}

and

\begin{center}
\PB{\&{bool} \\{planar}(\&{graph} ${}{\AND}\|G,\&{list}\langle\&{edge}%
\rangle{}$ ${}{\AND}\|P,{}$\&{bool} \\{embed}${}\K\\{false})$}.
\end{center}

Both take a directed graph \PB{\|G} and test it for planarity.
If the graph is planar and bidirected, i.e., for every edge of \PB{\|G} its
reversal is also in \PB{\|G}, and the argument \PB{\\{embed}} is true, then
they
also compute a combinatorial embedding of \PB{\|G} (by suitably reordering
its adjacency lists). If the graph \PB{\|G} is
non-planar then the first version of \PB{\\{planar}} only records that fact.
The second version in addition returns a subgraph of \PB{\|G} homeomorphic
to $K_{3,3}$ or $K_5$ (as a list \PB{\|P} of edges). For a planar graph
\PB{\|G} the running time of
both versions is linear (cf.\ section \ref{Efficiency} for more
detailed information). For non-planar graphs \PB{\|G} the
first version runs in linear time but the second version runs in
quadratic time.
We are aware of the linear time algorithm of Williamson
\cite{Williamson:Kuratowski} to find Kuratowski subgraphs but have
not implemented it.

The implementation of \PB{\\{planar}} is based on the LEDA platform of
combinatorial
and geometric computing \cite{LEDA-Manual,Mehlhorn-Naeher:LEDA}. It is part of
the LEDA-distribution (available through anonymous ftp at cs.uni-sb.de). In
this document we describe the implementation of both versions of \PB{%
\\{planar}} and a demo, and report on
our experimental experience.

Procedure \PB{\\{planar}} is based on the
Hopcroft and Tarjan linear time planarity testing algorithm as
described in \cite[section IV.10]{Me:book}. For the sequel we assume
knowledge of section IV.10 of \cite{Me:book}. A revised version of that section
is included in this document (see section \ref{reprint}) for the convenience
of the reader. Our procedure \PB{\\{planar}} differs from \cite[section
IV.10]{Me:book}
in two respects: Firstly, it works for arbitrary directed graphs and
not only for biconnected
undirected graphs. To this end we augment the input graph by additional edges
to make it biconnected and bidirected. The augmentation does not destroy
planarity. Secondly, the embedding
phase follows the
presentation in \cite{Mehlhorn-Mutzel:embedding}. We want to remark that the
description of the embedding phase given
in \cite[section IV.10]{Me:book} is false.
The essential part of \cite{Mehlhorn-Mutzel:embedding} is reprinted in
section \ref{embedding}.


This document defines the files \PB{$\\{planar}.\|h$}, \PB{$\\{planar}.\|c$},
and \PB{$\\{demo}.\|c$}.
\PB{$\\{planar}.\|c$} contains the code for procedure \PB{\\{planar}}, \PB{$%
\\{demo}.\|c$}
contains the code for a demo, and \PB{$\\{planar}.\|h$} consists of the
declarations of procedure \PB{\\{planar}}.
The third file is defined in section \ref{demo}, the structure of the first two
files
is as follows:

\Y\B\4\X1:\.{planar.h }\X${}\E{}$\6
\&{bool} \\{planar}(\&{graph} ${}{\AND}\|G,\39{}$\&{bool} \\{embed}${}\K%
\\{false});{}$\6
\&{bool} \\{planar}(\&{graph} ${}{\AND}\|G,\39\&{list}\langle\&{edge}\rangle{}$
${}{\AND}\|P,\39{}$\&{bool} \\{embed}${}\K\\{false});{}$\6
\&{void} \\{Make\_biconnected\_graph}(\&{graph} ${}{\AND}\|G){}$;\par
\fi

\M{2}

\Y\B\4\X2:\.{planar.c }\X${}\E{}$\6
\X3:includes\X;\6
\X11:typedefs, global variables and class declarations\X;\6
\X9:auxiliary functions\X;\6
\X5:first version of \PB{\\{planar}}\X;\6
\X4:second version of \PB{\\{planar}}\X;\par
\fi

\M{3}We include parts of LEDA (who would want to
work without it) \cite{LEDA-Manual,Mehlhorn-Naeher:LEDA}.
We need stacks, graphs, and graph algorithms.

\Y\B\4\X3:includes\X${}\E{}$\6
\8\#\&{include} \.{<LEDA/stack.h>}\6
\8\#\&{include} \.{<LEDA/graph.h>}\6
\8\#\&{include} \.{<LEDA/graph\_alg.h>}\6
\8\#\&{include} \.{"planar.h"}\par
\A36.
\Us2\ET35.\fi

\M{4}The second version of \PB{\\{planar}} is easy to describe. We first test
the
planarity of \PB{\|G} using the first version.
If \PB{\|G} is planar then we are done. If \PB{\|G} is
non-planar then we cycle through the edges of \PB{\|G}. For every edge \PB{\|e}
of
\PB{\|G} we test the planarity of \PB{$\|G-\|e$}. If \PB{$\|G-\|e$} is planar
we add \PB{\|e} back in.
In this way we determine a minimal (with respect to set inclusion)
non-planar subgraph of \PB{\|G}, i.e., either a $K_5$ or a $K_{3,3}$.

\Y\B\4\X4:second version of \PB{\\{planar}}\X${}\E{}$\6
\&{bool} \\{planar}(\&{graph} ${}{\AND}\|G,\39\&{list}\langle\&{edge}\rangle{}$
${}{\AND}\|P,\39{}$\&{bool} \\{embed}${}\K\\{false}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{if} ${}(\\{planar}(\|G,\39\\{embed})){}$\1\5
\&{return} \\{true};\C{ We work on a copy \PB{\|H} of \PB{\|G} since the
procedure alters \PB{\|G}; we link every vertex and edge of \PB{\|H} with its
original. For the vertices we also have the reverse links. }\2\7
${}\&{GRAPH}\langle\&{node},\39\&{edge}\rangle{}$ \|H;\6
${}\&{node\_array}\langle\&{node}\rangle{}$ \\{link}(\|G);\6
\&{node} \|v;\7
\&{forall\_nodes} ${}(\|v,\39\|G){}$\1\5
${}\\{link}[\|v]\K\|H.\\{new\_node}(\|v){}$;\C{ This requires some explanation.
\PB{$\|H.\\{new\_node}(\|v)$} adds a new node to \PB{\|H}, returns the new
node, and makes \PB{\|v} the information associated with the new node. So the
statement creates a copy of \PB{\|v} and bidirectionally links it with \PB{\|v}
}\2\7
\&{edge} \|e;\7
\&{forall\_edges} ${}(\|e,\39\|G){}$\1\5
${}\|H.\\{new\_edge}(\\{link}[\\{source}(\|e)],\39\\{link}[\\{target}(\|e)],\39%
\|e){}$;\C{ \PB{\\{link}[\\{source}(\|e)]} and \PB{\\{link}[\\{target}(\|e)]}
are the copies of \PB{\\{source}(\|e)} and \PB{\\{target}(\|e)} in \PB{\|H}.
The operation \PB{$\|H.\\{new\_edge}$} creates a new edge with these endpoints,
returns it, and makes \PB{\|e} the information of that edge. So the effect of
the loop is to make the edge set of \PB{\|H} a copy of the edge set of \PB{\|G}
and to let every edge of \PB{\|H} know its original. We can now determine a
minimal non-planar subgraph of \PB{\|H} }\2\7
${}\&{list}\langle\&{edge}\rangle{}$ \|L${}\K\|H.\\{all\_edges}(\,);{}$\6
\&{edge} \\{eh};\7
\&{forall} ${}(\\{eh},\39\|L){}$\5
${}\{{}$\1\6
${}\|e\K\|H[\\{eh}]{}$;\SHC{ the edge in \PB{\|G} corresponding to \PB{\\{eh}}
}\7
\&{node} \|x${}\K\\{source}(\\{eh});{}$\6
\&{node} \|y${}\K\\{target}(\\{eh});{}$\7
${}\|H.\\{del\_edge}(\\{eh});{}$\6
\&{if} (\\{planar}(\|H))\1\5
${}\|H.\\{new\_edge}(\|x,\39\|y,\39\|e){}$;\SHC{put a new version of \PB{%
\\{eh}} back in and establish the correspondence }\2\6
\4${}\}{}$\C{ \PB{\|H} is now a homeomorph of either $K_5$ or $K_{3,3}$. We
still need to translate back to \PB{\|G}. }\2\6
${}\|P.\\{clear}(\,);{}$\6
\&{forall\_edges} ${}(\\{eh},\39\|H){}$\1\5
${}\|P.\\{append}(\|H[\\{eh}]);{}$\2\6
\&{return} \\{false};\6
\4${}\}{}$\2\par
\U2.\fi

\M{5}The first version of \PB{\\{planar}} is also quite simple to describe.
Graphs with at most three
vertices are always planar. So assume that \PB{\|G} has more than three
vertices. We first add edges to \PB{\|G} to make it bidirected
and then add some more edges to make
it biconnected (of course, without destroying planarity). Then we test
the planarity of the extended graph and construct an embedding.
Since \PB{\\{planar}} alters the input graph, it works on a copy of it.



\Y\B\4\X5:first version of \PB{\\{planar}}\X${}\E{}$\6
\&{bool} \\{planar}(\&{graph} ${}{\AND}\\{Gin},\39{}$\&{bool} \\{embed}${}\K%
\\{false}{}$)\C{ \PB{\\{Gin}} is a directed graph. \PB{\\{planar}} decides
whether \PB{\\{Gin}} is planar. If it is and \PB{$\\{embed}\E\\{true}$} then it
also computes a  combinatorial embedding of \PB{\\{Gin}} by suitably reordering
its adjacency lists. \PB{\\{Gin}} must be bidirected in that case. }\1\1\6
$\{$ \&{int} \|n${}\K\\{Gin}.\\{number\_of\_nodes}(\,);{}$\7
\&{if} ${}(\|n\Z\T{3}){}$\1\5
\&{return} \\{true};\2\6
\&{if} ${}(\\{Gin}.\\{number\_of\_edges}(\,)>\T{6}*\|n-\T{12}){}$\1\5
\&{return} \\{false};\C{ An undirected planar graph has at most $3n-6$ edges; a
directed graph may have twice as many }\2\6
${}\\{cout}\LL\.{"number\ of\ nodes\ and}\)\.{\ edges\ \ "}\LL\|n\LL\.{"\ \ "}%
\LL\\{Gin}.\\{number\_of\_edges}(\,);{}$\6
\\{newline};\7
\&{float} \|T${}\K\\{used\_time}(\,);{}$\7
\X6:make \PB{\|G} a copy of \PB{\\{Gin}} and add edges to make \PB{\|G}
bidirected\X;\6
\X8:make \PB{\|G} biconnected\X;\6
${}\\{cout}\LL\.{"time\ to\ copy\ and\ to}\)\.{\ make\ bidirected\ and}\)\.{\
connected\ \ "}\LL\\{used\_time}(\|T);{}$\6
\\{newline};\6
\X13:test planarity\X;\6
${}\\{cout}\LL\.{"time\ to\ test\ planar}\)\.{ity\ \ \ "}\LL\\{used\_time}(%
\|T);{}$\6
\\{newline}; \&{if} (\\{embed}) $\{$ \&{if} (\\{Gin\_is\_bidirected}) %
\X26:construct embedding\X \6
\&{else}\1\5
${}\\{error\_handler}(\T{2},\39\.{"sorry:\ can\ only\ emb}\)\.{ed\ bidirected\
graphs}\)\.{"});{}$\2\6
${}\\{cout}\LL\.{"time\ to\ construct\ e}\)\.{mbedding\ \ \ "}\LL\\{used%
\_time}(\|T);{}$\6
\\{newline}; $\}$ \&{return} \\{true}; $\}{}$\par
\U2.\fi

\M{6}We make \PB{\|G} a copy of \PB{\\{Gin}} and bidirectionally link all
vertices and
edges. Then we add edges to \PB{\|G} to make it bidirected. In
\PB{\\{Gin\_is\_bidirected}} we record whether we needed to add edges.

\Y\B\4\X6:make \PB{\|G} a copy of \PB{\\{Gin}} and add edges to make \PB{\|G}
bidirected\X${}\E{}$\6
$\&{GRAPH}\langle\&{node},\39\&{edge}\rangle{}$ \|G;\6
${}\&{edge\_array}\langle\&{edge}\rangle{}$ \\{companion\_in\_G}(\\{Gin});\6
${}\&{node\_array}\langle\&{node}\rangle{}$ \\{link}(\\{Gin});\6
\&{bool} \\{Gin\_is\_bidirected}${}\K\\{true};{}$\7
${}\{{}$\1\6
\&{node} \|v;\7
\&{forall\_nodes} ${}(\|v,\39\\{Gin}){}$\1\5
${}\\{link}[\|v]\K\|G.\\{new\_node}(\|v){}$;\SHC{bidirectional links }\2\7
\&{edge} \|e;\7
\&{forall\_edges} ${}(\|e,\39\\{Gin}){}$\1\5
${}\\{companion\_in\_G}[\|e]\K\|G.\\{new\_edge}(\\{link}[\\{source}(\|e)],\39%
\\{link}[\\{target}(\|e)],\39\|e);{}$\2\6
\4${}\}{}$\2\6
\X7:bidirect G\X;\par
\U5.\fi

\M{7}We bidirect G. We first assign numbers to nodes and edges. We make sure
that
the two versions of the same undirected edge get the same number but versions
of distinct undirected edges get different numbers. Then we sort the edges
according to numbers. Finally we step through the sorted list of edges
and add
missing edges.


\Y\B\4\X7:bidirect G\X${}\E{}$\6
${}\{{}$\1\6
${}\&{node\_array}\langle\&{int}\rangle{}$ \\{nr}(\|G);\6
${}\&{edge\_array}\langle\&{int}\rangle{}$ \\{cost}(\|G);\6
\&{int} \\{cur\_nr}${}\K\T{0};{}$\6
\&{int} \|n${}\K\|G.\\{number\_of\_nodes}(\,);{}$\6
\&{node} \|v;\6
\&{edge} \|e;\7
\&{forall\_nodes} ${}(\|v,\39\|G){}$\1\5
${}\\{nr}[\|v]\K\\{cur\_nr}\PP;{}$\2\6
\&{forall\_edges} ${}(\|e,\39\|G){}$\1\5
${}\\{cost}[\|e]\K((\\{nr}[\\{source}(\|e)]<\\{nr}[\\{target}(\|e)])\?\|n*%
\\{nr}[\\{source}(\|e)]+\\{nr}[\\{target}(\|e)]:\|n*\\{nr}[\\{target}(\|e)]+%
\\{nr}[\\{source}(\|e)]);{}$\2\6
${}\|G.\\{sort\_edges}(\\{cost});{}$\7
${}\&{list}\langle\&{edge}\rangle{}$ \|L${}\K\|G.\\{all\_edges}(\,);{}$\7
\&{while} ${}(\R\|L.\\{empty}(\,)){}$\5
${}\{{}$\1\6
${}\|e\K\|L.\\{pop}(\,){}$;\C{ check whether the first edge on \PB{\|L} is
equal to the reversal of \PB{\|e}. If so, delete it from \PB{\|L}, if not, add
the reversal to \PB{\|G} }\6
\&{if} ${}(\R\|L.\\{empty}(\,)\W(\\{source}(\|e)\E\\{target}(\|L.\\{head}(\,)))%
\W(\\{source}(\|L.\\{head}(\,))\E\\{target}(\|e))){}$\1\5
${}\|L.\\{pop}(\,);{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\|G.\\{new\_edge}(\\{target}(\|e),\39\\{source}(\|e));{}$\6
${}\\{Gin\_is\_bidirected}\K\\{false};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U6.\fi

\N{1}{8}Making the Graph Biconnected.

We make \PB{\|G} biconnected. We first make it connected by linking all
roots. Assume that is done. Let $a$ be any articulation
point and let $u$ and $v$ be neighbors of $a$ belonging to different
biconnected components. Then there are embeddings of the two components
with the edges $\{u,a\}$ and $\{v,a\}$ on the boundary of the unbounded
face. Hence we may add the edge $\{u,v\}$ without destroying planarity.
Proceeding in this way we make \PB{\|G}
biconnected.

In \PB{\\{Make\_biconnected\_graph}} we change the graph while working on it.
But we modify only
those adjacency lists that will not be touched later.

We need the biconnected version of \PB{\|G} (\PB{\|G} will be further modified
during the planarity test) in order to construct the planar embedding. So we
store it as a graph \PB{\|H}. For every edge of \PB{\\{Gin}} and \PB{\|G} we
store a link to
its copy in \PB{\|H}. In addition every edge of \PB{\|H} is made to know its
reversal.

\Y\B\4\X8:make \PB{\|G} biconnected\X${}\E{}$\6
\\{Make\_biconnected\_graph}(\|G);\6
\X12:make \PB{\|H} a copy of \PB{\|G}\X;\par
\U5.\fi

\M{9}We give the details of the procedure \PB{\\{Make\_biconnected\_graph}}. We
first make \PB{\|G}
connected by linking all roots of the DFS-forest. In a second step we make
\PB{\|G} biconnected.

\Y\B\4\X9:auxiliary functions\X${}\E{}$\6
\&{void} \\{Make\_biconnected\_graph}(\&{graph} ${}{\AND}\|G){}$\1\1\2\2\6
${}\{{}$\1\6
\&{node} \|v;\6
${}\&{node\_array}\langle\&{bool}\rangle{}$ ${}\\{reached}(\|G,\39%
\\{false});{}$\6
\&{node} \|u${}\K\|G.\\{first\_node}(\,);{}$\7
\&{forall\_nodes} ${}(\|v,\39\|G){}$\5
${}\{{}$\1\6
\&{if} ${}(\R\\{reached}[\|v]){}$\5
${}\{{}$\C{ explore the connected component with root \PB{\|v} }\1\6
${}\\{DFS}(\|G,\39\|v,\39\\{reached});{}$\6
\&{if} ${}(\|u\I\|v){}$\5
${}\{{}$\C{ link \PB{\|v}'s component to the first component }\1\6
${}\|G.\\{new\_edge}(\|u,\39\|v);{}$\6
${}\|G.\\{new\_edge}(\|v,\39\|u);{}$\6
\4${}\}{}$\SHC{end if }\2\6
\4${}\}{}$\SHC{ end not reached }\2\6
\4${}\}{}$\SHC{end forall }\C{ \PB{\|G} is now connected. We next make it
biconnected. }\2\6
\&{forall\_nodes} ${}(\|v,\39\|G){}$\1\5
${}\\{reached}[\|v]\K\\{false};{}$\2\7
${}\&{node\_array}\langle\&{int}\rangle{}$ \\{dfsnum}(\|G);\6
${}\&{node\_array}\langle\&{node}\rangle{}$ ${}\\{parent}(\|G,\39\\{nil});{}$\6
\&{int} \\{dfs\_count}${}\K\T{0};{}$\6
${}\&{node\_array}\langle\&{int}\rangle{}$ \\{lowpt}(\|G);\7
${}\\{dfs\_in\_make\_biconnected\_graph}(\|G,\39\|G.\\{first\_node}(\,),\39%
\\{dfs\_count},\39\\{reached},\39\\{dfsnum},\39\\{lowpt},\39\\{parent});{}$\6
\4${}\}{}$\SHC{ end \PB{\\{Make\_biconnected\_graph}} }\2\par
\As10, 15, 16, 18\ETs27.
\U2.\fi

\M{10}We still have to give the procedure \PB{\\{dfs\_in\_make\_biconnected%
\_graph}}. It determines
articulation points and adds appropriate edges whenever it discovers one.
For a proof of correctness we refer the reader to
\cite[section IV.6]{Me:book}.

\Y\B\4\X9:auxiliary functions\X${}\mathrel+\E{}$\6
\&{void} \\{dfs\_in\_make\_biconnected\_graph}(\&{graph} ${}{\AND}\|G,\39{}$%
\&{node} \|v${},\39{}$\&{int} ${}{\AND}\\{dfs\_count},\39\&{node\_array}\langle%
\&{bool}\rangle{}$ ${}{\AND}\\{reached},\3{-1}\39\&{node\_array}\langle\&{int}%
\rangle{}$ ${}{\AND}\\{dfsnum},\39\&{node\_array}\langle\&{int}\rangle{}$ ${}{%
\AND}\\{lowpt},\39\&{node\_array}\langle\&{node}\rangle{}$ ${}{\AND}%
\\{parent}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{node} \|w;\6
\&{edge} \|e;\7
${}\\{dfsnum}[\|v]\K\\{dfs\_count}\PP;{}$\6
${}\\{lowpt}[\|v]\K\\{dfsnum}[\|v];{}$\6
${}\\{reached}[\|v]\K\\{true};{}$\6
\&{if} ${}(\R\|G.\\{first\_adj\_edge}(\|v)){}$\1\5
\&{return};\SHC{no children }\2\7
\&{node} \|u${}\K\\{target}(\|G.\\{first\_adj\_edge}(\|v)){}$;\SHC{first child
}\7
\&{forall\_adj\_edges} ${}(\|e,\39\|v){}$\5
${}\{{}$\1\6
${}\|w\K\\{target}(\|e);{}$\6
\&{if} ${}(\R\\{reached}[\|w]){}$\5
${}\{{}$\C{ e is a tree edge }\1\6
${}\\{parent}[\|w]\K\|v;{}$\6
${}\\{dfs\_in\_make\_biconnected\_graph}(\|G,\39\|w,\39\\{dfs\_count},\39%
\\{reached},\39\\{dfsnum},\39\\{lowpt},\39\\{parent});{}$\6
\&{if} ${}(\\{lowpt}[\|w]\E\\{dfsnum}[\|v]){}$\5
${}\{{}$\C{ \PB{\|v} is an articulation point. We now add an edge. If \PB{\|w}
is the first child and \PB{\|v} has a parent then we connect \PB{\|w} and \PB{%
\\{parent}[\|v]}, if \PB{\|w} is a first child and \PB{\|v} has no parent then
we do nothing. If \PB{\|w} is not the first child then we connect \PB{\|w} to
the first child. The net effect of all of this is to link all children of an
articulation point to the first child and the first child to the parent (if it
exists) }\1\6
\&{if} ${}(\|w\E\|u\W\\{parent}[\|v]){}$\5
${}\{{}$\1\6
${}\|G.\\{new\_edge}(\|w,\39\\{parent}[\|v]);{}$\6
${}\|G.\\{new\_edge}(\\{parent}[\|v],\39\|w);{}$\6
\4${}\}{}$\2\6
\&{if} ${}(\|w\I\|u){}$\5
${}\{{}$\1\6
${}\|G.\\{new\_edge}(\|u,\39\|w);{}$\6
${}\|G.\\{new\_edge}(\|w,\39\|u);{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\SHC{ end if lowpt = dfsnum }\2\6
${}\\{lowpt}[\|v]\K\\{Min}(\\{lowpt}[\|v],\39\\{lowpt}[\|w]);{}$\6
\4${}\}{}$\SHC{end tree edge }\2\6
\&{else}\1\5
${}\\{lowpt}[\|v]\K\\{Min}(\\{lowpt}[\|v],\39\\{dfsnum}[\|w]){}$;\SHC{non tree
edge }\2\6
\4${}\}{}$\SHC{ end forall }\2\6
\4${}\}{}$\SHC{end dfs }\2\par
\fi

\M{11}Because we use the function \PB{\\{dfs\_in\_make\_biconnected\_graph}}
before its declaration,
let's add it to the global declarations.

\Y\B\4\X11:typedefs, global variables and class declarations\X${}\E{}$\6
\&{void} \\{dfs\_in\_make\_biconnected\_graph}(\&{graph} ${}{\AND}\|G,\39{}$%
\&{node} \|v${},\39{}$\&{int} ${}{\AND}\\{dfs\_count},\39\&{node\_array}\langle%
\&{bool}\rangle{}$ ${}{\AND}\\{reached},\3{-1}\39\&{node\_array}\langle\&{int}%
\rangle{}$ ${}{\AND}\\{dfsnum},\39\&{node\_array}\langle\&{int}\rangle{}$ ${}{%
\AND}\\{lowpt},\39\&{node\_array}\langle\&{node}\rangle{}$ ${}{\AND}%
\\{parent}){}$;\par
\As14, 17\ETs20.
\U2.\fi

\M{12}We make \PB{\|H} a copy of \PB{\|G} and create bidirectional links
between the
vertices and edges of \PB{\|G} and \PB{\|H}.
Also, each edge in \PB{\\{Gin}} gets a link to its copy in \PB{\|H} and every
edge
of \PB{\|H} gets to know its reversal. More precisely, \PB{$\|H[\|G[\|v]]\K%
\|v$} for every
node \PB{\|v} of \PB{\|G} and \PB{$\|H[\|G[\|e]]\K\|e$} for every edge \PB{\|e}
of \PB{\|G}, and
\PB{\\{companion\_in\_H}[\\{ein}]} is the edge in \PB{\|H} corresponding to the
edge
\PB{\\{ein}} of \PB{\\{Gin}} for every edge \PB{\\{ein}} of \PB{\\{Gin}}.
Finally, if \PB{$\|e\K(\|u,\|v)$} is
an edge of \PB{\|H} then \PB{$\\{reversal}[\|e]\K(\|v,\|u)$}.



\Y\B\4\X12:make \PB{\|H} a copy of \PB{\|G}\X${}\E{}$\6
$\&{GRAPH}\langle\&{node},\39\&{edge}\rangle{}$ \|H;\6
${}\&{edge\_array}\langle\&{edge}\rangle{}$ \\{companion\_in\_H}(\\{Gin});\7
${}\{{}$\1\6
\&{node} \|v;\7
\&{forall\_nodes} ${}(\|v,\39\|G){}$\1\5
${}\|G.\\{assign}(\|v,\39\|H.\\{new\_node}(\|v));{}$\2\7
\&{edge} \|e;\7
\&{forall\_edges} ${}(\|e,\39\|G){}$\1\5
${}\|G.\\{assign}(\|e,\39\|H.\\{new\_edge}(\|G[\\{source}(\|e)],\39\|G[%
\\{target}(\|e)],\39\|e));{}$\2\7
\&{edge} \\{ein};\7
\&{forall\_edges} ${}(\\{ein},\39\\{Gin}){}$\1\5
${}\\{companion\_in\_H}[\\{ein}]\K\|G[\\{companion\_in\_G}[\\{ein}]];{}$\2\6
\4${}\}{}$\2\7
${}\&{edge\_array}\langle\&{edge}\rangle{}$ \\{reversal}(\|H);\7
${}\\{compute\_correspondence}(\|H,\39\\{reversal}){}$;\par
\U8.\fi

\N{1}{13}The Planarity Test.

We are now ready for the planarity test proper. We follow
\cite[page 95]{Me:book}. We first compute \PB{\\{dfsnumber}}s and \PB{%
\\{parent}}s, we
delete all forward edges and all reversals of tree edges, and we
reorder the adjaceny lists as described in \cite[page 101]{Me:book}.
We then test the strong planarity.
The array \PB{\\{alpha}} is needed for the embedding process. It
records the placement of the subsegments.



\Y\B\4\X13:test planarity\X${}\E{}$\6
$\&{node\_array}\langle\&{int}\rangle{}$ \\{dfsnum}(\|G);\6
${}\&{node\_array}\langle\&{node}\rangle{}$ ${}\\{parent}(\|G,\39\\{nil});{}$\7
${}\\{reorder}(\|G,\39\\{dfsnum},\39\\{parent});{}$\7
${}\&{edge\_array}\langle\&{int}\rangle{}$ ${}\\{alpha}(\|G,\39\T{0});{}$\7
${}\{{}$\1\6
${}\&{list}\langle\&{int}\rangle{}$ \\{Att};\7
${}\\{alpha}[\|G.\\{first\_adj\_edge}(\|G.\\{first\_node}(\,))]\K\\{left};{}$\6
\&{if} ${}(\R\\{strongly\_planar}(\|G.\\{first\_adj\_edge}(\|G.\\{first\_node}(%
\,)),\39\|G,\39\\{Att},\39\\{alpha},\39\\{dfsnum},\39\\{parent})){}$\1\5
\&{return} \\{false};\2\6
\4${}\}{}$\2\par
\U5.\fi

\M{14}We need two global constants \PB{\\{left}} and \PB{\\{right}}.

\Y\B\4\X11:typedefs, global variables and class declarations\X${}\mathrel+\E{}$%
\6
\&{const} \&{int} \\{left}${}\K\T{1};{}$\6
\&{const} \&{int} \\{right}${}\K\T{2}{}$;\par
\fi

\M{15}We give the details of the procedure \PB{\\{reorder}}. It first performs
DFS
to compute \PB{\\{dfsnum}}, \PB{\\{parent}}, \PB{\\{lowpt1}} and \PB{%
\\{lowpt2}}, and the list \PB{\\{Del}}
of all forward edges and all reversals of tree edges.
It then deletes the edges in \PB{\\{Del}} and finally it
reorders the edges.

\Y\B\4\X9:auxiliary functions\X${}\mathrel+\E{}$\6
\&{void} \\{reorder}(\&{graph} ${}{\AND}\|G,\39\&{node\_array}\langle\&{int}%
\rangle{}$ ${}{\AND}\\{dfsnum},\39\&{node\_array}\langle\&{node}\rangle{}$ ${}{%
\AND}\\{parent}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{node} \|v;\6
${}\&{node\_array}\langle\&{bool}\rangle{}$ ${}\\{reached}(\|G,\39%
\\{false});{}$\6
\&{int} \\{dfs\_count}${}\K\T{0};{}$\6
${}\&{list}\langle\&{edge}\rangle{}$ \\{Del};\6
${}\&{node\_array}\langle\&{int}\rangle{}$ \\{lowpt1}(\|G)${},{}$ \\{lowpt2}(%
\|G);\7
${}\\{dfs\_in\_reorder}(\\{Del},\39\|G.\\{first\_node}(\,),\39\\{dfs\_count},%
\39\\{reached},\39\\{dfsnum},\39\\{lowpt1},\39\\{lowpt2},\39\\{parent}){}$;\C{
remove forward and reversals of tree edges }\7
\&{edge} \|e;\7
\&{forall} ${}(\|e,\39\\{Del}){}$\1\5
${}\|G.\\{del\_edge}(\|e){}$;\C{ we now reorder adjacency lists as described in
\cite[page 101]{Me:book} }\2\7
\&{node} \|w;\6
${}\&{edge\_array}\langle\&{int}\rangle{}$ \\{cost}(\|G);\7
\&{forall\_edges} ${}(\|e,\39\|G){}$\5
${}\{{}$\1\6
${}\|v\K\\{source}(\|e);{}$\6
${}\|w\K\\{target}(\|e);{}$\6
${}\\{cost}[\|e]\K((\\{dfsnum}[\|w]<\\{dfsnum}[\|v])\?\T{2}*\\{dfsnum}[\|w]:((%
\\{lowpt2}[\|w]\G\\{dfsnum}[\|v])\?\T{2}*\\{lowpt1}[\|w]:\T{2}*\\{lowpt1}[\|w]+%
\T{1}));{}$\6
\4${}\}{}$\2\6
${}\|G.\\{sort\_edges}(\\{cost});{}$\6
\4${}\}{}$\2\par
\fi

\M{16}We still have to give the procedure \PB{\\{dfs\_in\_reorder}}. It's a bit
long but standard.

\Y\B\4\X9:auxiliary functions\X${}\mathrel+\E{}$\6
\&{void} \\{dfs\_in\_reorder}${}(\&{list}\langle\&{edge}\rangle{}$ ${}{\AND}%
\\{Del},\39{}$\&{node} \|v${},\39{}$\&{int} ${}{\AND}\\{dfs\_count},\39\&{node%
\_array}\langle\&{bool}\rangle{}$ ${}{\AND}\\{reached},\3{-1}\39\&{node\_array}%
\langle\&{int}\rangle{}$ ${}{\AND}\\{dfsnum},\39\&{node\_array}\langle\&{int}%
\rangle{}$ ${}{\AND}\\{lowpt1},\39\&{node\_array}\langle\&{int}\rangle{}$ ${}{%
\AND}\\{lowpt2},\3{-1}\39\&{node\_array}\langle\&{node}\rangle{}$ ${}{\AND}%
\\{parent}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{node} \|w;\6
\&{edge} \|e;\7
${}\\{dfsnum}[\|v]\K\\{dfs\_count}\PP;{}$\6
${}\\{lowpt1}[\|v]\K\\{lowpt2}[\|v]\K\\{dfsnum}[\|v];{}$\6
${}\\{reached}[\|v]\K\\{true};{}$\6
\&{forall\_adj\_edges} ${}(\|e,\39\|v){}$\5
${}\{{}$\1\6
${}\|w\K\\{target}(\|e);{}$\6
\&{if} ${}(\R\\{reached}[\|w]){}$\5
${}\{{}$\C{ e is a tree edge }\1\6
${}\\{parent}[\|w]\K\|v;{}$\6
${}\\{dfs\_in\_reorder}(\\{Del},\39\|w,\39\\{dfs\_count},\39\\{reached},\39%
\\{dfsnum},\39\\{lowpt1},\39\\{lowpt2},\39\\{parent});{}$\6
${}\\{lowpt1}[\|v]\K\\{Min}(\\{lowpt1}[\|v],\39\\{lowpt1}[\|w]);{}$\6
\4${}\}{}$\SHC{end tree edge }\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{lowpt1}[\|v]\K\\{Min}(\\{lowpt1}[\|v],\39\\{dfsnum}[\|w]){}$;\SHC{ no
effect for forward edges }\6
\&{if} ${}((\\{dfsnum}[\|w]\G\\{dfsnum}[\|v])\V\|w\E\\{parent}[\|v]{}$)\C{
forward edge or reversal of tree edge }\1\6
${}\\{Del}.\\{append}(\|e);{}$\2\6
\4${}\}{}$\SHC{end non-tree edge }\2\6
\4${}\}{}$\SHC{ end forall }\C{ we know \PB{\\{lowpt1}[\|v]} at this point and
now make a second pass over all      adjacent edges of \PB{\|v} to compute \PB{%
\\{lowpt2}} }\2\6
\&{forall\_adj\_edges} ${}(\|e,\39\|v){}$\5
${}\{{}$\1\6
${}\|w\K\\{target}(\|e);{}$\6
\&{if} ${}(\\{parent}[\|w]\E\|v){}$\5
${}\{{}$\C{ tree edge }\1\6
\&{if} ${}(\\{lowpt1}[\|w]\I\\{lowpt1}[\|v]){}$\1\5
${}\\{lowpt2}[\|v]\K\\{Min}(\\{lowpt2}[\|v],\39\\{lowpt1}[\|w]);{}$\2\6
${}\\{lowpt2}[\|v]\K\\{Min}(\\{lowpt2}[\|v],\39\\{lowpt2}[\|w]);{}$\6
\4${}\}{}$\SHC{end tree edge }\2\6
\&{else}\SHC{ all other edges }\6
\&{if} ${}(\\{lowpt1}[\|v]\I\\{dfsnum}[\|w]){}$\1\5
${}\\{lowpt2}[\|v]\K\\{Min}(\\{lowpt2}[\|v],\39\\{dfsnum}[\|w]);{}$\2\6
\4${}\}{}$\SHC{end forall }\2\6
\4${}\}{}$\SHC{end dfs }\2\par
\fi

\M{17}Because we use the function \PB{\\{dfs\_in\_reorder}} before its
declaration,
let's add it to the global declarations.

\Y\B\4\X11:typedefs, global variables and class declarations\X${}\mathrel+\E{}$%
\6
\&{void} \\{dfs\_in\_reorder}${}(\&{list}\langle\&{edge}\rangle{}$ ${}{\AND}%
\\{Del},\39{}$\&{node} \|v${},\39{}$\&{int} ${}{\AND}\\{dfs\_count},\39\&{node%
\_array}\langle\&{bool}\rangle{}$ ${}{\AND}\\{reached},\3{-1}\39\&{node\_array}%
\langle\&{int}\rangle{}$ ${}{\AND}\\{dfsnum},\39\&{node\_array}\langle\&{int}%
\rangle{}$ ${}{\AND}\\{lowpt1},\39\&{node\_array}\langle\&{int}\rangle{}$ ${}{%
\AND}\\{lowpt2},\3{-1}\39\&{node\_array}\langle\&{node}\rangle{}$ ${}{\AND}%
\\{parent}){}$;\par
\fi

\M{18}We now come to the heart of the planarity test: procedure \PB{\\{strongly%
\_planar}}.
It takes a tree edge $e0 = (x,y)$ and tests whether
the segment $S(e0)$ is strongly planar. If  successful it returns  (in \PB{%
\\{Att}}) the
ordered list of attachments of $S(e0)$ (excluding $x$); high DFS-numbers are
at the front of the list. In \PB{\\{alpha}} it
records the placement of the subsegments.

\PB{\\{strongly\_planar}} operates in three phases. It first constructs the
cycle $C(e0)$
underlying the segment $S(e0)$. It then constructs the interlacing graph for
the
segments emanating from the spine of the cycle. If this graph is non-bipartite
then the segment $S(e0)$ is non-planar. If it is bipartite then the segment is
planar. In this case the third phase checks whether the segment is strongly
planar and, if so, computes its list of attachments.


\Y\B\4\X9:auxiliary functions\X${}\mathrel+\E{}$\6
\&{bool} \\{strongly\_planar}(\&{edge} \\{e0}${},\39{}$\&{graph} ${}{\AND}\|G,%
\39\&{list}\langle\&{int}\rangle{}$ ${}{\AND}\\{Att},\39\&{edge\_array}\langle%
\&{int}\rangle{}$ ${}{\AND}\\{alpha},\3{-1}\39\&{node\_array}\langle\&{int}%
\rangle{}$ ${}{\AND}\\{dfsnum},\39\&{node\_array}\langle\&{node}\rangle{}$ ${}{%
\AND}\\{parent}){}$\1\1\2\2\6
${}\{{}$\1\6
\X19:determine the cycle $C(e0)$\X;\6
\X21:process all edges leaving the spine\X;\6
\X25:test strong planarity and compute \PB{\\{Att}}\X;\6
\&{return} \\{true};\6
\4${}\}{}$\2\par
\fi

\M{19}We determine the cycle $C(e0)$ by following first edges until a back
edge is encountered. \PB{\\{wk}} will be the last node on the tree path and %
\PB{\\{w0}}
is the destination of the back edge. This agrees with the
notation of \cite{Me:book}.


\Y\B\4\X19:determine the cycle $C(e0)$\X${}\E{}$\6
\&{node} \|x${}\K\\{source}(\\{e0});{}$\6
\&{node} \|y${}\K\\{target}(\\{e0});{}$\6
\&{edge} \|e${}\K\|G.\\{first\_adj\_edge}(\|y);{}$\6
\&{node} \\{wk}${}\K\|y;{}$\7
\&{while} ${}(\\{dfsnum}[\\{target}(\|e)]>\\{dfsnum}[\\{wk}]{}$)\SHC{ e is a
tree edge }\6
${}\{{}$\1\6
${}\\{wk}\K\\{target}(\|e);{}$\6
${}\|e\K\|G.\\{first\_adj\_edge}(\\{wk});{}$\6
\4${}\}{}$\2\7
\&{node} \\{w0}${}\K\\{target}(\|e){}$;\par
\U18.\fi

\M{20}The second phase of \PB{\\{strongly\_planar}} constructs the connected
components of
the interlacing graph of the segments emananating from the the spine of the
cycle $C(e0)$. We call a connected component a {\em block}. For each block
we store the segments comprising its left and right side (lists
\PB{\\{Lseg}} and \PB{\\{Rseg}} contain the edges
defining these segments) and the ordered list of attachments of the segments
in the block; lists \PB{\\{Latt}} and \PB{\\{Ratt}} contain the DFS-numbers of
the
attachments; high DFS-numbers are at the front of the list. Blocks are
so important that we make them a class.

We need the following operations on blocks.

The constructor takes an edge and a list of attachments and creates
a block having the edge as the only segment in its left side.

\PB{\\{flip}} interchanges the two sides of a block.

\PB{\\{head\_of\_Latt}} and \PB{\\{head\_of\_Ratt}} return the first elements
on \PB{\\{Latt}} and \PB{\\{Ratt}} respectively
and \PB{\\{Latt\_empty}} and \PB{\\{Ratt\_empty}} check these lists for
emptyness.

\PB{\\{left\_interlace}} checks whether the block interlaces with the left side
of the topmost block of
stack \PB{\|S}. \PB{\\{right\_interlace}} does the same for the right side.

\PB{\\{combine}} combines the block with another block \PB{\\{Bprime}} by
simply concatenating all
lists.

\PB{\\{clean}} removes the attachment \PB{\|w} from the block \PB{\|B} (it is
guaranteed to be the
first attachment of \PB{\|B}). If the block becomes empty then it records the
placement of all segments in the block in the array \PB{\\{alpha}} and returns
true.
Otherwise it returns false.

\PB{\\{add\_to\_Att}} first makes sure that the right side has no attachment
above \PB{\\{w0}}
(by
flipping); when \PB{\\{add\_to\_Att}} is called at least one side has no
attachment above \PB{\\{w0}}.
\PB{\\{add\_to\_Att}} then adds the lists \PB{\\{Ratt}} and \PB{\\{Latt}} to
the output list \PB{\\{Att}}
and records the placement of all segments in the block in \PB{\\{alpha}}.
We advise the reader to only skim the rest of the section at this
point and to come back to it when the procedures are first used.


\Y\B\4\X11:typedefs, global variables and class declarations\X${}\mathrel+\E{}$%
\6
\&{class} \&{block} ${}\{{}$\1\6
\4\&{private}:\5
${}\&{list}\langle\&{int}\rangle{}$ \\{Latt}${},{}$ \\{Ratt};\SHC{list of
attachments }\6
${}\&{list}\langle\&{edge}\rangle{}$ \\{Lseg}${},{}$ \\{Rseg};\SHC{list of
segments represented by their defining edges }\7
\4\&{public}:\5
\&{block}(\&{edge} \|e${},\39\&{list}\langle\&{int}\rangle{}$ ${}{\AND}\|A){}$%
\1\1\2\2\6
${}\{{}$\1\6
${}\\{Lseg}.\\{append}(\|e);{}$\6
${}\\{Latt}.\\{conc}(\|A){}$;\SHC{ the other two lists are empty }\6
\4${}\}{}$\2\7
${}\CM\&{block}{}$(\,)\5
${}\{\,\}{}$\7
\&{void} \\{flip}(\,)\1\1\2\2\6
${}\{{}$\1\6
${}\&{list}\langle\&{int}\rangle{}$ \\{ha};\6
${}\&{list}\langle\&{edge}\rangle{}$ \\{he};\C{ we first interchange \PB{%
\\{Latt}} and \PB{\\{Ratt}} and then \PB{\\{Lseg}} and \PB{\\{Rseg}} }\7
${}\\{ha}.\\{conc}(\\{Ratt}){}$;\5
${}\\{Ratt}.\\{conc}(\\{Latt}){}$;\5
${}\\{Latt}.\\{conc}(\\{ha});{}$\6
${}\\{he}.\\{conc}(\\{Rseg}){}$;\5
${}\\{Rseg}.\\{conc}(\\{Lseg}){}$;\5
${}\\{Lseg}.\\{conc}(\\{he});{}$\6
\4${}\}{}$\2\7
\&{int} \\{head\_of\_Latt}(\,)\5
${}\{{}$\5
\1\&{return} ${}\\{Latt}.\\{head}(\,){}$;\5
${}\}{}$\2\7
\&{bool} \\{empty\_Latt}(\,)\5
${}\{{}$\5
\1\&{return} ${}\\{Latt}.\\{empty}(\,){}$;\5
${}\}{}$\2\7
\&{int} \\{head\_of\_Ratt}(\,)\5
${}\{{}$\5
\1\&{return} ${}\\{Ratt}.\\{head}(\,){}$;\5
${}\}{}$\2\7
\&{bool} \\{empty\_Ratt}(\,)\5
${}\{{}$\5
\1\&{return} ${}\\{Ratt}.\\{empty}(\,){}$;\5
${}\}{}$\2\7
\&{bool} \\{left\_interlace}${}(\&{stack}\langle{}$\&{block} ${}{*}\rangle{}$
${}{\AND}\|S){}$\1\1\2\2\6
${}\{{}$\C{ check for interlacing with the left side of the topmost block of %
\PB{\|S} }\1\6
\&{if} ${}(\\{Latt}.\\{empty}(\,)){}$\1\5
${}\\{error\_handler}(\T{1},\39\.{"Latt\ is\ never\ empty}\)\.{"});{}$\2\6
\&{if} ${}(\R\|S.\\{empty}(\,)\W\R((\|S.\\{top}(\,))\MG\\{empty\_Latt}(\,))\W%
\\{Latt}.\\{tail}(\,)<(\|S.\\{top}(\,))\MG\\{head\_of\_Latt}(\,)){}$\1\5
\&{return} \\{true};\2\6
\&{else}\1\5
\&{return} \\{false};\2\6
\4${}\}{}$\2\7
\&{bool} \\{right\_interlace}${}(\&{stack}\langle{}$\&{block} ${}{*}\rangle{}$
${}{\AND}\|S){}$\1\1\2\2\6
${}\{{}$\C{ check for interlacing with the right side of the topmost block of %
\PB{\|S} }\1\6
\&{if} ${}(\\{Latt}.\\{empty}(\,)){}$\1\5
${}\\{error\_handler}(\T{1},\39\.{"Latt\ is\ never\ empty}\)\.{"});{}$\2\6
\&{if} ${}(\R\|S.\\{empty}(\,)\W\R((\|S.\\{top}(\,))\MG\\{empty\_Ratt}(\,))\W%
\\{Latt}.\\{tail}(\,)<(\|S.\\{top}(\,))\MG\\{head\_of\_Ratt}(\,)){}$\1\5
\&{return} \\{true};\2\6
\&{else}\1\5
\&{return} \\{false};\2\6
\4${}\}{}$\2\7
\&{void} \\{combine}(\&{block} ${}{*}{\AND}\\{Bprime}){}$\1\1\2\2\6
${}\{{}$\C{ add block Bprime to the rear of \PB{$\this$} block }\1\6
${}\\{Latt}.\\{conc}(\\{Bprime}\MG\\{Latt});{}$\6
${}\\{Ratt}.\\{conc}(\\{Bprime}\MG\\{Ratt});{}$\6
${}\\{Lseg}.\\{conc}(\\{Bprime}\MG\\{Lseg});{}$\6
${}\\{Rseg}.\\{conc}(\\{Bprime}\MG\\{Rseg});{}$\6
\&{delete} (\\{Bprime});\6
\4${}\}{}$\2\7
\&{bool} \\{clean}(\&{int} \\{dfsnum\_w}${},\39\&{edge\_array}\langle\&{int}%
\rangle{}$ ${}{\AND}\\{alpha},\39\&{node\_array}\langle\&{int}\rangle{}$ ${}{%
\AND}\\{dfsnum}){}$\1\1\2\2\6
${}\{{}$\C{ remove all attachments to \PB{\|w}; there may be several }\1\6
\&{while} ${}(\R\\{Latt}.\\{empty}(\,)\W\\{Latt}.\\{head}(\,)\E\\{dfsnum%
\_w}){}$\1\5
${}\\{Latt}.\\{pop}(\,);{}$\2\6
\&{while} ${}(\R\\{Ratt}.\\{empty}(\,)\W\\{Ratt}.\\{head}(\,)\E\\{dfsnum%
\_w}){}$\1\5
${}\\{Ratt}.\\{pop}(\,);{}$\2\6
\&{if} ${}(\R\\{Latt}.\\{empty}(\,)\V\R\\{Ratt}.\\{empty}(\,)){}$\1\5
\&{return} \\{false};\C{\PB{\\{Latt}} and \PB{\\{Ratt}} are empty; we record
the placement of the subsegments in \PB{\\{alpha}}. }\2\7
\&{edge} \|e;\7
\&{forall} ${}(\|e,\39\\{Lseg}){}$\1\5
${}\\{alpha}[\|e]\K\\{left};{}$\2\6
\&{forall} ${}(\|e,\39\\{Rseg}){}$\1\5
${}\\{alpha}[\|e]\K\\{right};{}$\2\6
\&{return} \\{true};\6
\4${}\}{}$\2\7
\&{void} \\{add\_to\_Att}${}(\&{list}\langle\&{int}\rangle{}$ ${}{\AND}\\{Att},%
\39{}$\&{int} \\{dfsnum\_w0}${},\39\&{edge\_array}\langle\&{int}\rangle{}$ ${}{%
\AND}\\{alpha},\3{-1}\39\&{node\_array}\langle\&{int}\rangle{}$ ${}{\AND}%
\\{dfsnum}){}$\1\1\2\2\6
${}\{{}$\C{ add the block to the rear of \PB{\\{Att}}. Flip if necessary }\1\6
\&{if} ${}(\R\\{Ratt}.\\{empty}(\,)\W\\{head\_of\_Ratt}(\,)>\\{dfsnum\_w0}){}$%
\1\5
\\{flip}(\,);\2\6
${}\\{Att}.\\{conc}(\\{Latt});{}$\6
${}\\{Att}.\\{conc}(\\{Ratt}){}$;\C{ This needs some explanation. Note that %
\PB{\\{Ratt}} is either empty or $\{w0\}$. Also if \PB{\\{Ratt}} is non-empty
then all subsequent sets are contained in $\{w0\}$. So we indeed compute an
ordered set of attachments. }\7
\&{edge} \|e;\7
\&{forall} ${}(\|e,\39\\{Lseg}){}$\1\5
${}\\{alpha}[\|e]\K\\{left};{}$\2\6
\&{forall} ${}(\|e,\39\\{Rseg}){}$\1\5
${}\\{alpha}[\|e]\K\\{right};{}$\2\6
\4${}\}{}$\2\2\6
${}\}{}$;\par
\fi

\M{21}We process the edges leaving the spine of $S(e0)$ starting at node \PB{%
\\{wk}}
and working backwards. The interlacing graph of the segments emanating from
the cycle is represented as a stack \PB{\|S} of blocks.

\Y\B\4\X21:process all edges leaving the spine\X${}\E{}$\6
\&{node} \|w${}\K\\{wk};{}$\6
${}\&{stack}\langle{}$\&{block} ${}{*}\rangle{}$ \|S;\7
\&{while} ${}(\|w\I\|x){}$\5
${}\{{}$\1\6
\&{int} \\{count}${}\K\T{0};{}$\7
\&{forall\_adj\_edges} ${}(\|e,\39\|w){}$\5
${}\{{}$\1\6
${}\\{count}\PP;{}$\6
\&{if} ${}(\\{count}\I\T{1}{}$)\SHC{no action for first edge }\6
${}\{{}$\1\6
\X22:test recursively\X;\6
\X23:update stack \PB{\|S} of attachments\X;\6
\4${}\}{}$\SHC{ end if }\2\6
\4${}\}{}$\SHC{end forall }\2\6
\X24:prepare for next iteration\X;\6
${}\|w\K\\{parent}[\|w];{}$\6
\4${}\}{}$\SHC{end while }\2\par
\U18.\fi

\M{22}Let $e$ be any edge leaving the spine. We need to test whether
$S(e)$ is strongly planar and if so compute its list \PB{\|A} of attachments.
If $e$ is a tree edge we call our procedure recursively and if $e$ is a
back edge then $S(e)$ is certainly strongly planar and \PB{\\{target}(\|e)} is
the only attachment. If we detect non-planarity we return flase and free
the storage allocated for the blocks of stack \PB{\|S}.


\Y\B\4\X22:test recursively\X${}\E{}$\6
$\&{list}\langle\&{int}\rangle{}$ \|A;\7
\&{if} ${}(\\{dfsnum}[\|w]<\\{dfsnum}[\\{target}(\|e)]){}$\5
${}\{{}$\C{ tree edge }\1\6
\&{if} ${}(\R\\{strongly\_planar}(\|e,\39\|G,\39\|A,\39\\{alpha},\39\\{dfsnum},%
\39\\{parent})){}$\5
${}\{{}$\1\6
\&{while} ${}(\R\|S.\\{empty}(\,)){}$\1\5
\&{delete} ${}(\|S.\\{pop}(\,));{}$\2\6
\&{return} \\{false};\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\|A.\\{append}(\\{dfsnum}[\\{target}(\|e)]){}$;\SHC{ a back edge }\2\par
\U21.\fi

\M{23}The list \PB{\|A} contains the ordered list of attachments of segment
$S(e)$. We create an new block consisting only of segment $S(e)$ (in its
$L$-part) and then combine this block with the topmost block of stack \PB{\|S}
as
long as
there is interlacing. We check for interlacing with the $L$-part. If there
is interlacing then we flip the two sides of the topmost block. If there
is still interlacing with the left side then the interlacing graph is
non-bipartite and
we declare the graph non-planar (and also free the storage allocated
for the blocks). Otherwise we check for interlacing with
the R-part. If there is interlacing then we combine \PB{\|B} with the topmost
block and repeat the process with the new topmost block. If there is no
interlacing then we push block \PB{\|B} onto \PB{\|S}.



\Y\B\4\X23:update stack \PB{\|S} of attachments\X${}\E{}$\6
\&{block} ${}{*}\|B\K{}$\&{new} \&{block} ${}(\|e,\39\|A);{}$\7
\&{while} (\\{true})\5
${}\{{}$\1\6
\&{if} ${}(\|B\MG\\{left\_interlace}(\|S)){}$\1\5
${}(\|S.\\{top}(\,))\MG\\{flip}(\,);{}$\2\6
\&{if} ${}(\|B\MG\\{left\_interlace}(\|S)){}$\5
${}\{{}$\1\6
\&{delete} (\|B);\6
\&{while} ${}(\R\|S.\\{empty}(\,)){}$\1\5
\&{delete} ${}(\|S.\\{pop}(\,));{}$\2\6
\&{return} \\{false};\6
\4${}\}{}$\2\6
;\6
\&{if} ${}(\|B\MG\\{right\_interlace}(\|S)){}$\1\5
${}\|B\MG\\{combine}(\|S.\\{pop}(\,));{}$\2\6
\&{else}\1\5
\&{break};\2\6
\4${}\}{}$\SHC{end while }\2\6
${}\|S.\\{push}(\|B){}$;\par
\U21.\fi

\M{24}We have now processed all edges emanating from vertex \PB{\|w}. Before
starting to
process edges emanating from vertex \PB{\\{parent}[\|w]} we remove \PB{%
\\{parent}[\|w]} from
the list of attachments of the topmost block of stack \PB{\|S}. If this block
becomes empty then we pop it from the stack and record the placement for all
segments in the block in array \PB{\\{alpha}}.

\Y\B\4\X24:prepare for next iteration\X${}\E{}$\6
\&{while} ${}(\R\|S.\\{empty}(\,)\W(\|S.\\{top}(\,))\MG\\{clean}(\\{dfsnum}[%
\\{parent}[\|w]],\39\\{alpha},\39\\{dfsnum})){}$\1\5
\&{delete} ${}(\|S.\\{pop}(\,)){}$;\2\par
\U21.\fi

\M{25}We test the strong planarity of the segment $S(e0)$.

We know at this point that the
interlacing graph is bipartite. Also for each of its connected components the
corresponding block on stack \PB{\|S} contains the list of attachments below %
\PB{\|x}.
Let \PB{\|B} be the topmost block of \PB{\|S}. If both sides of \PB{\|B} have
an attachment
above \PB{\\{w0}} then $S(e0)$ is not strongly planar. We free the storage
allocated for
the blocks and return false. Otherwise (cf. procedure
\PB{\\{add\_to\_Att}}) we first make sure that the right side of \PB{\|B}
attaches only to \PB{\\{w0}}
(if at all) and then add the two sides of \PB{\|B} to the output list \PB{%
\\{Att}}. We also
record the placements of the subsegments in \PB{\\{alpha}}.

\Y\B\4\X25:test strong planarity and compute \PB{\\{Att}}\X${}\E{}$\6
$\\{Att}.\\{clear}(\,);{}$\6
\&{while} ${}(\R\|S.\\{empty}(\,)){}$\5
${}\{{}$\1\6
\&{block} ${}{*}\|B\K\|S.\\{pop}(\,);{}$\7
\&{if} ${}(\R(\|B\MG\\{empty\_Latt}(\,))\W\R(\|B\MG\\{empty\_Ratt}(\,))\W(\|B%
\MG\\{head\_of\_Latt}(\,)>\\{dfsnum}[\\{w0}])\W(\|B\MG\\{head\_of\_Ratt}(\,)>%
\\{dfsnum}[\\{w0}])){}$\5
${}\{{}$\1\6
\&{delete} (\|B);\6
\&{while} ${}(\R\|S.\\{empty}(\,)){}$\1\5
\&{delete} ${}(\|S.\\{pop}(\,));{}$\2\6
\&{return} \\{false};\6
\4${}\}{}$\2\6
${}\|B\MG\\{add\_to\_Att}(\\{Att},\39\\{dfsnum}[\\{w0}],\39\\{alpha},\39%
\\{dfsnum});{}$\6
\&{delete} (\|B);\6
\4${}\}{}$\SHC{end while }\C{ Let's not forget (as the book does) that $w0$ is
an attachment of $S(e0)$ except if $w0 = x$. }\2\6
\&{if} ${}(\\{w0}\I\|x){}$\1\5
${}\\{Att}.\\{append}(\\{dfsnum}[\\{w0}]){}$;\2\par
\U18.\fi

\N{1}{26}Constructing the Embedding.    \label{embedding}



%%%%%%%%%%%%%%%%%% einbinden von bildern mit Unterschrift %%%%%%%%%%%%%

\newcommand{\bild}[2]{
\begin{figure}[htb]
\begin{center}
\input{#1.tex}
\end{center}
\caption{{#2}\label{#1}}
\end{figure}
}

%%%%%  wird so benutzt: \bild{<label>}{<caption>}  %%%%%%%%%%%%%%%%%%%%
%%%%%  z.B. \bild{part}{A part of the augmented segment tree structure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newtheorem{theorem}{Theorem}

We now discuss how the planarity testing algorithm can be extended
so that it also computes a planar map.
Consider a segment $S(e_0)=C+S(e_1)+\ldots +S(e_m)$ consisting of
cycle $C$ and emanating segments $S(e_1),\ldots ,S(e_m)$ and
recall that the proofs of Lemmas 8 and 9 describe how
the embeddings of the $S(e_i)$'s have to be combined to yield a
canonical embedding of $S(e_0)$.
Our goal is to turn these proofs into an efficient algorithm.

The proofs of Lemmas 8 and 9 demonstrate two things:
\begin{itemize}
\item How to test whether $IG(C)$ is bipartite and how to construct
a partition $\{L,R\}$ of its vertex set, and
\item how to construct an embedding of $S(e_0)$ from the embeddings of
the $S(e_i)$'s. This involves flipping of embeddings as we
incrementally construct the embedding of $S(e_0)$.
\end{itemize}

Suppose now that some benign agent told us that $IG(C)$ were bipartite
and gave us an appropriate partition $\{L,R\}$ of its vertex set,
i.e., a partition $\{L,R\}$ such that no
two segments in $L$ and no two segments in $R$ interlace and such that
$A(e_i)\cap \{w_1,\ldots ,w_{r-1}\}=\emptyset$ for any segment
$S(e_i)\in R$.
Here, as before, $w_0,\ldots ,w_r$ denotes the stem of $C$.
Then no flipping would ever be necessary;
we can simply combine the embeddings of the $S(e_i)$'s as prescribed
by the partition $\{L,R\}$.
More precisely, to construct a canonical embedding of $S(e_0)$ draw
the path $w_0,\ldots ,w_k$ (consisting of stem $w_0,\ldots ,w_r$,
edge $e_0 = (w_r,w_{r+1})$ and spine $w_{r+1},\ldots ,w_k$) as a
vertical upwards directed path, add edge $(w_k,w_0)$, and then for $i$,
$1\leq i\leq m$, and $S(e_i)\in L$ extend the embedding of
$C+S(e_1)+\ldots S(e_{i-1})$ by glueing a canonical embedding of
$S(e_i)$ onto the left side of the vertical path, and for $i$,
$1\leq i\leq m$, and $S(e_i)\in R$ extend the embedding of
$C+S(e_1)+\ldots +S(e_{i-1})$ by glueing a reversed canonical
embedding of $S(e_i)$ onto the right side of the vertical path.
Similarly, if the goal is to construct a reversed canonical embedding
of $S(e_0)$ then, if $S(e_i)\in L$, a reversed canonical embedding of
$S(e_i)$ is glued onto the right side of the vertical path, and if
$S(e_i) \in R$, then a canonical embedding of $S(e_i)$ is glued onto the
left side of the vertical path.

Who is the benign agent which tells us that $IG(C)$ is bipartite and
gives us the appropriate partition $\{L,R\}$ of the segments emanating
from $C=C(e_0)$?
It's the call {\em stronglyplanar}($e_0$).
After all, it tests whether $IG(C)$ is bipartite and computes a
bipartition of its vertex set.
Let $S(e)$ be a segment emanating from $C$ and let $B$ be the connected
component of $IG(C)$ containing $S(e)$.
The call {\em stronglyplanar}($e_0$) computes $B$ iteratively.
The construction of $B$ is certainly completed when $B$ is popped from
stack $S$.
Put $S(e)$ into $R$ when $S(e)\in RB$ at that moment and put $S(e)$
into $L$ otherwise.
With this extension, algorithm {\em stronglyplanar} computes the
partition $\{L,R\}$ of the segments emanating from $C$ in linear time.
We assume for notational convenience that the partition (more precisely,
the union of all partitions for all cycles $C(e_0)$ encountered in the
algorithm) is given as a function $\alpha :S\to \{L,R\}$ where $S$ is
the set of edges for which {\em stronglyplanar} is called.

We next give the algorithmic details of the embedding process.
We first use procedure {\em stronglyplanar} to compute the mapping
$\alpha$.
We then use a procedure {\em embedding} to actually compute an
embedding.
The procedure {\em embedding} takes two parameters: an edge $e_0$ and
a flag $t\in \{L,R\}$.
A call {\em embedding}($e_0,L$) computes a canonical embedding of
$S(e_0)$ and a call {\em embedding}($e_0,R$) computes a reversed
canonical embedding of $S(e_0)$.
The call {\em embedding}($(1,2),L$) embeds the entire graph.

The embedding of $S(e_0)$ computed by {\em embedding}$(e_0,t)$ is
represented in the following non-standard way:
\begin{enumerate}
\item For the vertices $v\in V(e_0)$ we use the standard
representation, i.e., the cyclic list of the incident
edges corresponding to the clockwise ordering of the edges
in the embedding.
\item For the vertices in the stem we use a non-standard representation.
For each vertex $w_i\in\{w_0,\ldots,w_{r}\}$ let the lists
$AL(w_i)$ and $AR(w_i)$ be such that the catenation of
$(w_i,w_{i+1})$, $AR(w_i)$, $(w_i,w_{i-1})$, and
$AL(w_i)$ corresponds to the clockwise ordering of the edges
incident to $w_i$ in the embedding. Here, $w_{-1}=w_k$.
Note that $AR(w_i)=\emptyset$ for $1\leq i<r$ if $t=L$, and
$AL(w_i)=\emptyset$ for $1\leq i<r$, if $t=R$.
The lists $AL(w_i)$, $AR(w_i)$, $0\leq i\leq r$, are returned in an
implicit way: $AL(w_r)$ and $AR(w_r)$ are returned as the list
$T=AL(w_r),(w_r,w_{r+1})$, $AR(w_r)$ and the other lists
are returned as the list $A=$ $AR(w_{r-1}),\ldots,$
$AR(w_0),(w_0,w_k),AL(w_0),\ldots ,AL(w_{r-1})$,
cf.\ Figure~\ref{result-embedding.pstex_t}.
\end{enumerate}

\bild{result-embedding.pstex_t}{A call {\em embedding} $(e_0,t)$ returns lists
$T$ and $A$.}


The procedure {\em embedding} has the same structure as the procedure
{\em stronglyplanar} and is given in Program 1 on page \pageref{program}.
It first constructs the stem and the spine (line (1)) of cycle $C(e_0)$,
then walks down the spine (lines (3) to (14)), and finally computes
the lists $T$ and $A$ it wants to return (lines (15) and (16)).

We first discuss the walk down the spine.
Suppose that the walk has reached vertex $w_j$.
We first recursively process the edges emanating from $w_j$
(lines (4) to (10)), and then compute the cyclic adjacency list of vertex
$w_j$ and prepare for the next iteration (lines (11) to (13)).

We discuss lines (4) to (10) first.
In general, some number of edges emanating from $w_j$ and all edges
incident to vertices $w_l$ with $l>j$ will have been processed already.
In agreement with our previous notation call the processed edges
$e_1,\ldots ,e_{i-1}$.
We claim that the following statement is an invariant of the loop (4) to (10):
$T$ concatenated with $(w_j,w_{j-1})$ is the cyclic adjacency list of
vertex $w_j$ in the embedding of $C+S(e_1)+\ldots +S(e_{i-1})$, and
$AL$ and $AR$ are the catenation of lists $AL(w_0),\ldots ,AL(w_{j-1})$
and $AR(w_{j-1}),\ldots ,AR(w_0)$ respectively where $(w_l,w_{l+1})$,
$AR(w_l), (w_l,w_{l-1}), AL(w_l)$ is the cyclic adjacency
list of vertex $w_l$, $0\leq l\leq j-1$, in the embedding of
$C+S(e_0)+\ldots +S(e_{i-1})$.
The lists $T$, $AL$, and $AR$ are certainly initialized correctly in
line (2).
Assume now that we process edge $e'=e_i$ emanating from $w_j$.
The flag $\alpha(e')$ indicates what kind of embedding of $S(e_i)$ is
needed to build a canonical embedding of $S(e_0)$; the opposite kind of
embedding of $S(e_i)$ is needed to build a reversed canonical embedding
of $S(e_0)$.
So the required kind is given by $t\oplus\alpha(e')$, where
$L\oplus L=R\oplus R=L$ and $L\oplus R=R\oplus L=R$.
The call {\em embedding}$(e',t\oplus\alpha(e'))$ computes the cyclic
adjacency lists of the vertices in $V(e')$ and returns lists $T'$ and
$A'$ as defined above.
If $S(e_i)$ has to be glued to the left side of the vertical path
$w_0,\ldots ,w_k$, i.e., if  $t=\alpha(e')$ then we append $T'$ to the front of
$T$ and $A'$ to
the end of $AL$, cf.\ Figure~\ref{glueing}.
Analogously, if $S(e_i)$ has to be glued to the right side of the
path $w_0,\ldots ,w_k$, i.e., if $t\not=\alpha(e')$, then we append $T'$
to the end of $T$ and $A'$ to the front of $AR$.
This clearly maintains the invariant.

Suppose now that we have processed all edges emanating from $w_j$.
Then $(w_j,w_{j-1})$ concatenated with $T$ is the cyclic adjacency list
of vertex $w_j$ (line (11)).

\begin{figure}[htb]
\begin{center}
\input{glueing.pstex_t}
\end{center}
\caption{\label{glueing}
Glueing $S(e')$ to the left or right side of the path
$w_0,\ldots ,w_k$ respectively.}
\end{figure}

We next prepare for the treatment of vertex $w_{j-1}$.
Let $T'$ and $T''$ be the list of darts incident to $w_{j-1}$ from
the left and from the right respectively and having their other
endpoint in an already embedded segment.
List $T'$ is a suffix of $AL$ and list $T''$ is a prefix of $AR$.
The catenation of $T',(w_{j-1},w_j)$, $T''$, and
$(w_{j-1},w_{j-2})$ is the current clockwise adjacency list of
vertex $w_{j-1}$.
Thus lines (12) and (13) correctly initialize $AL$, $AR$, and $T$ for
the next iteration.

Suppose now that all edges emanating from the spine of $C(e_0)$ have
been processed, i.e., control reaches line (15).
At this point, list $T$ is the ordered list of darts incident to $w_r$
(except $(w_r,w_{r-1})$) and the two lists $AL$ and $AR$ are the
ordered list of darts incident to the two sides of the stem of $C(e_0)$.
Thus $T$ and the catenation of $AR,(w_0,w_k)$, and
$AL$ are the two components of the output of {\em embedding}$(e_0,t)$.
We summarize in

\begin{theorem}
Let $G=(V,E)$ be a planar graph.
Then $G$ can be turned into a planar map $(G,\sigma)$ in linear time.
\end{theorem}
\begin{table}
~\hrulefill

\begin{tabbing}
\qquad \= {\bf do} \= {\bf do} \= \kill
\> (0) \' {\bf procedure} {\em embedding}($e_0$: edge, $t$: $\{L,R\}$)\+\\
($*$ computes an embedding of $S(e_0)$, $e_0=(x,y)$, as described in the text; %
\\
\> it returns the lists $T$ and $A$ defined in the text $*$)\-\\
\> (1) \' find the spine of segment $S(e_0)$ by starting in node $y$ and always%
\+\\
\> take the first edge of every adjacency list until a back edge is \\
\> encountered. This back edge leads to node $w_0=lowpt[y]$. \\
\> Let $w_0,\ldots,w_r$ be the tree path from $w_0$ to $x=w_r$ and \\
\> let $w_{r+1}=y,\ldots,w_k$ be the spine constructed above. \-\\
\> (2) \' $AL \gets AR \gets$ empty list of darts;\\
\>     \> $T \gets (w_k,w_0)$; \` ($*$ a list of darts $*$)\\
\> (3) \' {\bf for} $j$ {\bf from} $k$ {\bf downto} $r+1$ \\
\> (4) \' {\bf do} {\bf for} all edges $e'$ (except the first) emanating from
$w_j$ \\
\> (5) \' \> {\bf do} $(T',A') \gets$ {\em embedding}$(e',t\oplus\alpha(e'))$\\
\> (6) \' \> \> {\bf if} $t=\alpha(e')$\\
\> (7) \' \> \> {\bf then} $T \gets T'$ {\bf conc} $T$; $AL \gets AL$ {\bf
conc} $A'$\\
\> (8) \' \> \> {\bf else} $T \gets T$ {\bf conc} $T'$; $AR \gets A'$ {\bf
conc}  $AR$\\
\> (9) \' \> \> {\bf fi}\\
\>(10) \' \> {\bf od}\\
\>(11) \' \> {\bf output} $(w_j,w_{j-1})$ {\bf conc} $T$;
\` ($*$ the cyclic adjacency list of vertex $w_j$ $*$) \\
\>(12) \' \> {\bf let} $AL=AL'$ {\bf conc} $T'$ and $AR=T''$
{\bf conc} $AR'$\\
\>     \> \> where $T'$ and $T''$ contain all darts incident
to $w_{j-1}$;\\
\>(13) \' \> $AL\gets AL'$; $AR\gets AR'$; $T\gets
T'$ {\bf conc} $(w_{j-1},w_j)$ {\bf conc} $T''$\\
\>(14) \' {\bf od}\\
\>(15) \' $A\gets$ $AR$ {\bf conc} $(w_0,w_k)$ {\bf conc} $AL$;\\
\>(16) \' {\bf return} $T$ and $A$\\
\>(17) \' {\bf end}
\end{tabbing}

~\hrulefill Program 1 \label{program} \hrulefill

\end{table}






In our implementation we follow the book except in three minor points. \PB{\|G}
has only one directed
version of each edge but \PB{\|H} has both. In the embedding
phase we need both
directions and therefore construct the embedding of
\PB{\|H} and later translate it back to \PB{\\{Gin}}. Secondly, we do not
construct the embedding
of \PB{\|H} vertex by vertex but in one shot. To that effect we compute a
labelling
\PB{\\{sort\_num}} of the edges of \PB{\|H} and later sort the edges.
Thirdly, the book makes reference to edges $(w_{i-1},w_i)$
and their reversals. To make these edges available we compute an array \PB{%
\\{tree\_edge\_into}}
that contains for each node the incoming tree edge.


We finally want to remark on our convention for drawing lists.
In Figures \ref{result-embedding.pstex_t}
and \ref{glueing} the arrows indicate the end (!!!) of the lists.

\clearpage



\Y\B\4\X26:construct embedding\X${}\E{}$\6
${}\{{}$\1\6
${}\&{list}\langle\&{edge}\rangle{}$ \|T${},{}$ \|A;\SHC{lists of edges of \PB{%
\|H} }\6
\&{int} \\{cur\_nr}${}\K\T{0};{}$\6
${}\&{edge\_array}\langle\&{int}\rangle{}$ \\{sort\_num}(\|H);\6
${}\&{node\_array}\langle\&{edge}\rangle{}$ \\{tree\_edge\_into}(\|G);\7
${}\\{embedding}(\|G.\\{first\_adj\_edge}(\|G.\\{first\_node}(\,)),\39\\{left},%
\39\|G,\39\\{alpha},\39\\{dfsnum},\39\|T,\39\|A,\39\\{cur\_nr},\39\\{sort%
\_num},\39\\{tree\_edge\_into},\39\\{parent},\39\\{reversal}){}$;\C{ \PB{\|T}
contains all edges incident to the first node except the cycle edge into it.
That edge comprises \PB{\|A} }\6
${}\|T.\\{conc}(\|A);{}$\7
\&{edge} \|e;\7
\&{forall} ${}(\|e,\39\|T){}$\1\5
${}\\{sort\_num}[\|e]\K\\{cur\_nr}\PP;{}$\2\7
${}\&{edge\_array}\langle\&{int}\rangle{}$ \\{sort\_Gin}(\\{Gin});\7
${}\{{}$\1\6
\&{edge} \\{ein};\7
\&{forall\_edges} ${}(\\{ein},\39\\{Gin}){}$\1\5
${}\\{sort\_Gin}[\\{ein}]\K\\{sort\_num}[\\{companion\_in\_H}[\\{ein}]];{}$\2\6
\4${}\}{}$\2\6
${}\\{Gin}.\\{sort\_edges}(\\{sort\_Gin});{}$\6
\4${}\}{}$\2\par
\U5.\fi

\M{27}It remains to describe procedure \PB{\\{embedding}}.

\Y\B\4\X9:auxiliary functions\X${}\mathrel+\E{}$\6
\&{void} \\{embedding}(\&{edge} \\{e0}${},\39{}$\&{int} \|t${},\39\&{GRAPH}%
\langle\&{node},\39\&{edge}\rangle{}$ ${}{\AND}\|G,\39\&{edge\_array}\langle%
\&{int}\rangle{}$ ${}{\AND}\\{alpha},\3{-1}\39\&{node\_array}\langle\&{int}%
\rangle{}$ ${}{\AND}\\{dfsnum},\39\&{list}\langle\&{edge}\rangle{}$ ${}{\AND}%
\|T,\39\&{list}\langle\&{edge}\rangle{}$ ${}{\AND}\|A,\39{}$\&{int} ${}{\AND}%
\\{cur\_nr},\3{-1}\39\&{edge\_array}\langle\&{int}\rangle{}$ ${}{\AND}\\{sort%
\_num},\39\&{node\_array}\langle\&{edge}\rangle{}$ ${}{\AND}\\{tree\_edge%
\_into},\3{-1}\39\&{node\_array}\langle\&{node}\rangle{}$ ${}{\AND}\\{parent},%
\39\&{edge\_array}\langle\&{edge}\rangle{}$ ${}{\AND}\\{reversal}){}$\1\1\2\2\6
${}\{{}$\1\6
\X28:embed: determine the cycle $C(e0)$\X;\6
\X29:process the subsegments\X;\6
\X33:prepare the output\X;\6
\4${}\}{}$\2\par
\fi

\M{28}We start by determining the spine cycle. This is precisley as in \PB{%
\\{strongly\_planar}}.
We also record for the vertices $w_{r+1}$, $\ldots$, $w_k$, and $w_0$ the
incoming cycle edge either in \PB{\\{tree\_edge\_into}} or in the local
variable \PB{\\{back\_edge\_into\_w0}}. This is line (1) of Program1.

\Y\B\4\X28:embed: determine the cycle $C(e0)$\X${}\E{}$\6
\&{node} \|x${}\K\\{source}(\\{e0});{}$\6
\&{node} \|y${}\K\\{target}(\\{e0});{}$\7
${}\\{tree\_edge\_into}[\|y]\K\\{e0};{}$\7
\&{edge} \|e${}\K\|G.\\{first\_adj\_edge}(\|y);{}$\6
\&{node} \\{wk}${}\K\|y;{}$\7
\&{while} ${}(\\{dfsnum}[\\{target}(\|e)]>\\{dfsnum}[\\{wk}]{}$)\SHC{ e is a
tree edge }\6
${}\{{}$\1\6
${}\\{wk}\K\\{target}(\|e);{}$\6
${}\\{tree\_edge\_into}[\\{wk}]\K\|e;{}$\6
${}\|e\K\|G.\\{first\_adj\_edge}(\\{wk});{}$\6
\4${}\}{}$\2\7
\&{node} \\{w0}${}\K\\{target}(\|e);{}$\6
\&{edge} \\{back\_edge\_into\_w0}${}\K\|e{}$;\par
\U27.\fi

\M{29}Lines (2) to (14).

\Y\B\4\X29:process the subsegments\X${}\E{}$\6
\&{node} \|w${}\K\\{wk};{}$\6
${}\&{list}\langle\&{edge}\rangle{}$ \\{Al}${},{}$ \\{Ar};\6
${}\&{list}\langle\&{edge}\rangle{}$ \\{Tprime}${},{}$ \\{Aprime};\7
${}\|T.\\{clear}(\,);{}$\6
${}\|T.\\{append}(\|G[\|e]){}$;\SHC{ \PB{$\|e\K(\\{wk},\\{w0})$} at this point,
line (2) }\6
\&{while} ${}(\|w\I\|x){}$\5
${}\{{}$\1\6
\&{int} \\{count}${}\K\T{0};{}$\7
\&{forall\_adj\_edges} ${}(\|e,\39\|w){}$\5
${}\{{}$\1\6
${}\\{count}\PP;{}$\6
\&{if} ${}(\\{count}\I\T{1}{}$)\SHC{no action for first edge }\6
${}\{{}$\1\6
\X30:embed recursively\X;\6
\X31:update lists \PB{\|T}, \PB{\\{Al}}, and \PB{\\{Ar}}\X;\6
\4${}\}{}$\SHC{ end if }\2\6
\4${}\}{}$\SHC{end forall }\2\6
\X32:compute \PB{\|w}'s adjacency list and prepare for next iteration\X;\6
${}\|w\K\\{parent}[\|w];{}$\6
\4${}\}{}$\SHC{end while }\2\par
\U27.\fi

\M{30}Line (5). The book does not distinguish between tree and back edges but
we do
here.

\Y\B\4\X30:embed recursively\X${}\E{}$\6
\&{if} ${}(\\{dfsnum}[\|w]<\\{dfsnum}[\\{target}(\|e)]){}$\5
${}\{{}$\C{ tree edge }\1\6
\&{int} \\{tprime}${}\K((\|t\E\\{alpha}[\|e])\?\\{left}:\\{right});{}$\7
${}\\{embedding}(\|e,\39\\{tprime},\39\|G,\39\\{alpha},\39\\{dfsnum},\39%
\\{Tprime},\39\\{Aprime},\39\\{cur\_nr},\39\\{sort\_num},\39\\{tree\_edge%
\_into},\39\\{parent},\39\\{reversal});{}$\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\C{ back edge }\1\6
${}\\{Tprime}.\\{append}(\|G[\|e]){}$;\SHC{$e$ }\6
${}\\{Aprime}.\\{append}(\\{reversal}[\|G[\|e]]){}$;\SHC{reversal of $e$ }\6
\4${}\}{}$\2\par
\U29.\fi

\M{31}Lines (6) to (9).

\Y\B\4\X31:update lists \PB{\|T}, \PB{\\{Al}}, and \PB{\\{Ar}}\X${}\E{}$\6
\&{if} ${}(\|t\E\\{alpha}[\|e]){}$\5
${}\{{}$\1\6
${}\\{Tprime}.\\{conc}(\|T);{}$\6
${}\|T.\\{conc}(\\{Tprime}){}$;\SHC{$T = Tprime\ conc\ T$ }\6
${}\\{Al}.\\{conc}(\\{Aprime}){}$;\SHC{$Al = Al\ conc\ Aprime$ }\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\|T.\\{conc}(\\{Tprime}){}$;\SHC{ $ T\ = T\ conc\ Tprime $ }\6
${}\\{Aprime}.\\{conc}(\\{Ar});{}$\6
${}\\{Ar}.\\{conc}(\\{Aprime}){}$;\SHC{ $ Ar\ = Aprime\ conc\ Ar$ }\6
\4${}\}{}$\2\par
\U29.\fi

\M{32}Lines (11) to (13).

\Y\B\4\X32:compute \PB{\|w}'s adjacency list and prepare for next iteration%
\X${}\E{}$\6
$\|T.\\{append}(\\{reversal}[\|G[\\{tree\_edge\_into}[\|w]]]){}$;\SHC{
$(w_{j-1},w_j)$ }\6
\&{forall} ${}(\|e,\39\|T){}$\1\5
${}\\{sort\_num}[\|e]\K\\{cur\_nr}\PP{}$;\C{ \PB{\|w}'s adjacency list is now
computed; we clear \PB{\|T} and prepare for the next iteration by moving all
darts incident to \PB{\\{parent}[\|w]} from \PB{\\{Al}} and \PB{\\{Ar}} to \PB{%
\|T}. These darts are at the rear end of \PB{\\{Al}} and at the front end of %
\PB{\\{Ar}} }\2\6
${}\|T.\\{clear}(\,);{}$\6
\&{while} ${}(\R\\{Al}.\\{empty}(\,)\W\\{source}(\\{Al}.\\{tail}(\,))\E\|G[%
\\{parent}[\|w]]{}$)\SHC{ \PB{\\{parent}[\|w]} is in \PB{\|G}, \PB{$\\{Al}.%
\\{tail}$} in \PB{\|H} }\6
${}\{{}$\1\6
${}\|T.\\{push}(\\{Al}.\\{Pop}(\,)){}$;\SHC{Pop removes from the rear }\6
\4${}\}{}$\2\6
${}\|T.\\{append}(\|G[\\{tree\_edge\_into}[\|w]]){}$;\SHC{ push would be
equivalent }\6
\&{while} ${}(\R\\{Ar}.\\{empty}(\,)\W\\{source}(\\{Ar}.\\{head}(\,))\E\|G[%
\\{parent}[\|w]]{}$)\SHC{ }\6
${}\{{}$\1\6
${}\|T.\\{append}(\\{Ar}.\\{pop}(\,)){}$;\SHC{ pop removes from the front }\6
\4${}\}{}$\2\par
\U29.\fi

\M{33}Line (15). Concatenate \PB{\\{Ar}}, $(w_0,w_r)$, and \PB{\\{Al}}.

\Y\B\4\X33:prepare the output\X${}\E{}$\6
$\|A.\\{clear}(\,);{}$\6
${}\|A.\\{conc}(\\{Ar});{}$\6
${}\|A.\\{append}(\\{reversal}[\|G[\\{back\_edge\_into\_w0}]]);{}$\6
${}\|A.\\{conc}(\\{Al}){}$;\par
\U27.\fi

\N{1}{34}Efficiency. \label{Efficiency}

Under LEDA 3.0 the space requirement of the first version of \PB{\\{planar}} is
approximately
$160 (n+m) +100 \alpha m$ Bytes, where $n$ and $m$ denote the number of nodes
and edges respectively and $\alpha$ is the fraction of edges in the input graph
that do not have their reversal in the input graph. For the pseudo-random
planar graphs generated in the demo we have $\alpha = 0$ and $m = 4n$ and hence
the
space requirement is about $800 n$ Bytes. The second version needs an
additional
$54n + 66m$ Bytes.

The running time of \PB{\\{planar}} is about $50$ times the running
time of \PB{\\{STRONG\_COMPONENTS}}. On a 50 MIPS SPARC10 workstation
the planarity of a
planar graph with 16000 nodes and 30000 edges ($\alpha = 0$) is tested in
about 10 seconds. It takes 5.4 seconds to make the graph bidirected and
biconnected, about 3.9 seconds to test its planarity, and
another 6.1 seconds to
construct an embedding. The space requirement is about 15 MByte.



\fi

\N{1}{35}A Demo. \label{demo}

The demo allows the user to either interactively construct a graph
using
LEDA's graph editor or to construct a random graph, or to
construct a ``pseudo-random'' planar graph
(the graph defined by an arrangement of random line segments). The graph is
then tested for
planarity. If the graph is planar a straight-line embedding is output. If the
graph is non-planar a Kuratowski subgraph is highlighted.

The demo proceeds in cycles. In each cycle we first clear the graphics window %
\PB{\|W} and
the graph \PB{\|G} and then give the user the choice of a new input graph.


\Y\B\4\X35:\.{demo.c }\X${}\E{}$\6
\X3:includes\X;\6
\X37:procedure to draw graphs\X;\6
\\{main}(\,)\1\1 $\{$ \X38:initiation and declarations\X;\6
\&{while} (\\{true}) $\{$ \X39:select graph\X;\6
\X40:test graph for planarity and show output\X \X41:reset window\X;\6
$\}$ \&{return} \T{0}; $\}{}$\par
\fi

\M{36}We need to include \PB{$\\{planar}.\|h$} and various parts of LEDA.

\Y\B\4\X3:includes\X${}\mathrel+\E{}$\6
\8\#\&{include} \.{"planar.h"}\6
\8\#\&{include} \.{<LEDA/graph.h>}\6
\8\#\&{include} \.{<LEDA/graph\_alg.h>}\6
\8\#\&{include} \.{<LEDA/window.h>}\6
\8\#\&{include} \.{<LEDA/graph\_edit.h>}\par
\fi

\M{37}We need a simple procedure to draw a graph in a graphics window. The
numbering of the nodes is optional.

\Y\B\4\X37:procedure to draw graphs\X${}\E{}$\6
\&{void} \\{draw\_graph}(\&{const} \&{GRAPH}${}\langle\&{point},\39\&{int}%
\rangle{}$ ${}{\AND}\|G,\39{}$\&{window} ${}{\AND}\|W,\39{}$\&{bool} %
\\{numbering}${}\K\\{false}){}$\1\1\2\2\6
${}\{{}$\1\6
\&{node} \|v;\6
\&{edge} \|e;\6
\&{int} \|i${}\K\T{0};{}$\7
\&{forall\_edges} ${}(\|e,\39\|G){}$\1\5
${}\|W.\\{draw\_edge}(\|G[\\{source}(\|e)],\39\|G[\\{target}(\|e)],\39%
\\{blue});{}$\2\6
\&{if} (\\{numbering})\1\6
\&{forall\_nodes} ${}(\|v,\39\|G){}$\1\5
${}\|W.\\{draw\_int\_node}(\|G[\|v],\39\|i\PP,\39\\{red});{}$\2\2\6
\&{else}\1\6
\&{forall\_nodes} ${}(\|v,\39\|G){}$\1\5
${}\|W.\\{draw\_filled\_node}(\|G[\|v],\39\\{red});{}$\2\2\6
\4${}\}{}$\2\par
\U35.\fi

\M{38}We give the user a short explanation of the demo and declare some
variables.


\Y\B\4\X38:initiation and declarations\X${}\E{}$\6
\&{panel} \|P;\7
${}\|P.\\{text\_item}(\.{"This\ demo\ illustrat}\)\.{es\ planarity\ testing}\)%
\.{\ and\ planar\ straight}\)\.{-line"});{}$\6
${}\|P.\\{text\_item}(\.{"embedding.\ You\ have}\)\.{\ two\ ways\ to\ constru}%
\)\.{ct\ a\ graph:\ either\ i}\)\.{nteractively"});{}$\6
${}\|P.\\{text\_item}(\.{"using\ the\ LEDA\ grap}\)\.{h\ editor\ or\ by\ calli}%
\)\.{ng\ one\ of\ two\ graph\ }\)\.{generators."});{}$\6
${}\|P.\\{text\_item}(\.{"The\ first\ generator}\)\.{\ constructs\ a\ random}\)%
\.{\ graph\ with\ a\ certai}\)\.{n"});{}$\6
${}\|P.\\{text\_item}(\.{"number\ of\ nodes\ and}\)\.{\ edges\ (you\ will\ be\
}\)\.{asked\ how\ many)\ and\ }\)\.{the\ "});{}$\6
${}\|P.\\{text\_item}(\.{"second\ generator\ co}\)\.{nstructs\ a\ planar\ gr}\)%
\.{aph\ \ by\ intersecting}\)\.{\ a\ certain"});{}$\6
${}\|P.\\{text\_item}(\.{"number\ of\ random\ li}\)\.{ne\ segments\ in\ the\ u}%
\)\.{nit\ square\ (you\ will}\)\.{\ be\ asked\ how\ many).}\)\.{"});{}$\6
${}\|P.\\{text\_item}(\.{"\ "});{}$\6
${}\|P.\\{text\_item}(\.{"The\ graph\ is\ displa}\)\.{yed\ and\ then\ tested\ }%
\)\.{for\ planarity."});{}$\6
${}\|P.\\{text\_item}(\.{"If\ the\ graph\ is\ non}\)\.{-planar\ a\ Kuratowski}%
\)\.{\ subgraph\ is\ highlig}\)\.{hted."});{}$\6
${}\|P.\\{text\_item}(\.{"If\ the\ graph\ is\ pla}\)\.{nar,\ a\ straight-line}%
\)\.{\ drawing\ is\ produced}\)\.{."});{}$\6
${}\|P.\\{button}(\.{"continue"});{}$\6
${}\|P.\\{open}(\,);{}$\7
\&{window} \|W;\6
${}\&{GRAPH}\langle\&{point},\39\&{int}\rangle{}$ \|G;\6
\&{node} \|v${},{}$ \|w;\6
\&{edge} \|e;\6
\&{int} \|n${}\K\T{250};{}$\6
\&{int} \|m${}\K\T{250};{}$\6
\&{const} \&{double} \\{pi}${}\K\T{3.14};{}$\6
\&{panel} \\{P1}(\.{"PLANARITY\ TEST"});\7
${}\\{P1}.\\{int\_item}(\.{"|V|\ =\ "},\39\|n,\39\T{0},\39\T{500});{}$\6
${}\\{P1}.\\{int\_item}(\.{"|E|\ =\ "},\39\|m,\39\T{0},\39\T{500});{}$\6
${}\\{P1}.\\{button}(\.{"edit"});{}$\6
${}\\{P1}.\\{button}(\.{"random"});{}$\6
${}\\{P1}.\\{button}(\.{"planar"});{}$\6
${}\\{P1}.\\{button}(\.{"quit"});{}$\6
${}\\{P1}.\\{text\_item}(\.{"\ "});{}$\6
${}\\{P1}.\\{text\_item}(\.{"The\ first\ slider\ as}\)\.{ks\ for\ the\ number\
n\ }\)\.{of\ nodes\ and"});{}$\6
${}\\{P1}.\\{text\_item}(\.{"the\ second\ slider\ a}\)\.{sks\ for\ the\ number\
m}\)\.{\ of\ edges."});{}$\6
${}\\{P1}.\\{text\_item}(\.{"If\ you\ select\ the\ r}\)\.{andom\ input\ button\
t}\)\.{hen\ a\ graph\ with"});{}$\6
${}\\{P1}.\\{text\_item}(\.{"that\ number\ of\ node}\)\.{s\ and\ edges\ is\
const}\)\.{ructed,\ if\ you"});{}$\6
${}\\{P1}.\\{text\_item}(\.{"select\ the\ planar\ i}\)\.{nput\ button\ then\
2.5}\)\.{\ times\ square-root\ o}\)\.{f\ n"});{}$\6
${}\\{P1}.\\{text\_item}(\.{"random\ line\ segment}\)\.{s\ are\ chosen\ and\
int}\)\.{ersected\ to\ yield"});{}$\6
${}\\{P1}.\\{text\_item}(\.{"a\ planar\ graph\ with}\)\.{\ about\ n\ nodes,\
and\ }\)\.{if\ you\ select\ the"});{}$\6
${}\\{P1}.\\{text\_item}(\.{"edit\ button\ then\ th}\)\.{e\ graph\ editor\ is\
ca}\)\.{lled."});{}$\6
${}\\{P1}.\\{text\_item}(\.{"\ "}){}$;\par
\U35.\fi

\M{39}We display the panel \PB{\\{P1}} until the user makes his choice. Then we
construct
the appropriate graph.

\Y\B\4\X39:select graph\X${}\E{}$\6
\&{int} \\{inp}${}\K\\{P1}.\\{open}(\|W){}$;\SHC{ P1 is displayed until a
button is pressed }\7
\&{if} ${}(\\{inp}\E\T{3}){}$\1\5
\&{break};\SHC{ quit button pressed }\2\6
${}\|W.\\{init}(\T{0},\39\T{1000},\39\T{0});{}$\6
${}\|W.\\{set\_node\_width}(\T{5});{}$\6
\&{switch} (\\{inp})\5
${}\{{}$\1\6
\4\&{case} \T{0}:\6
${}\{{}$\SHC{ graph editor }\1\6
${}\|W.\\{set\_node\_width}(\T{10});{}$\6
${}\|G.\\{clear}(\,);{}$\6
${}\\{graph\_edit}(\|W,\39\|G,\39\\{false});{}$\6
\&{break};\6
\4${}\}{}$\2\6
\4\&{case} \T{1}:\6
${}\{{}$\SHC{ random graph }\1\6
${}\|G.\\{clear}(\,);{}$\6
${}\\{random\_graph}(\|G,\39\|n,\39\|m){}$;\C{ eliminate parallel edges and
self-loops }\6
\\{eliminate\_parallel\_edges}(\|G);\7
${}\&{list}\langle\&{edge}\rangle{}$ \\{Del}${}\K\|G.\\{all\_edges}(\,);{}$\7
\&{forall} ${}(\|e,\39\\{Del}){}$\1\6
\&{if} ${}(\|G.\\{source}(\|e)\E\|G.\\{target}(\|e)){}$\1\5
${}\|G.\\{del\_edge}(\|e){}$;\C{ draw the graph with its nodes on a circle}\2\2%
\7
\&{float} \\{ang}${}\K\T{0};{}$\7
\&{forall\_nodes} ${}(\|v,\39\|G){}$\5
${}\{{}$\1\6
${}\|G[\|v]\K\&{point}(\T{500}+\T{400}*\\{sin}(\\{ang}),\39\T{500}+\T{400}*%
\\{cos}(\\{ang}));{}$\6
${}\\{ang}\MRL{+{\K}}\T{2}*\\{pi}/\|n;{}$\6
\4${}\}{}$\2\6
${}\\{draw\_graph}(\|G,\39\|W);{}$\6
\&{break};\6
\4${}\}{}$\2\6
\4\&{case} \T{2}:\6
${}\{{}$\SHC{ pseudo-random planar graph }\1\6
${}\&{node\_array}\langle\&{double}\rangle{}$ \\{xcoord}(\|G);\6
${}\&{node\_array}\langle\&{double}\rangle{}$ \\{ycoord}(\|G);\7
${}\|G.\\{clear}(\,);{}$\6
${}\\{random\_planar\_graph}(\|G,\39\\{xcoord},\39\\{ycoord},\39\|n);{}$\6
\&{forall\_nodes} ${}(\|v,\39\|G){}$\1\5
${}\|G[\|v]\K\&{point}(\T{1000}*\\{xcoord}[\|v],\39\T{900}*\\{ycoord}[\|v]);{}$%
\2\6
${}\\{draw\_graph}(\|G,\39\|W);{}$\6
\&{break};\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U35.\fi

\M{40}We test the planarity of our graph \PB{\|G} using our procedure \PB{%
\\{planar}}.

\Y\B\4\X40:test graph for planarity and show output\X${}\E{}$\6
\&{if} ${}(\\{PLANAR}(\|G,\39\\{false})){}$\5
${}\{{}$\1\6
\&{if} ${}(\|G.\\{number\_of\_nodes}(\,)<\T{4}){}$\1\5
${}\|W.\\{message}(\.{"That's\ an\ insult:\ E}\)\.{very\ graph\ with\ |V|\ }\)%
\.{<=\ 4\ is\ planar"});{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\|W.\\{message}(\.{"G\ is\ planar.\ I\ comp}\)\.{ute\ a\ straight-line\ }\)%
\.{embedding\ ..."}){}$;\C{ we first make \PB{\|G} bidirected. We remember the
edges added in \PB{\\{n\_edges}} }\7
${}\&{node\_array}\langle\&{int}\rangle{}$ \\{nr}(\|G);\6
${}\&{edge\_array}\langle\&{int}\rangle{}$ \\{cost}(\|G);\6
\&{int} \\{cur\_nr}${}\K\T{0};{}$\6
\&{int} \|n${}\K\|G.\\{number\_of\_nodes}(\,);{}$\6
\&{node} \|v;\6
\&{edge} \|e;\7
\&{forall\_nodes} ${}(\|v,\39\|G){}$\1\5
${}\\{nr}[\|v]\K\\{cur\_nr}\PP;{}$\2\6
\&{forall\_edges} ${}(\|e,\39\|G){}$\1\5
${}\\{cost}[\|e]\K((\\{nr}[\\{source}(\|e)]<\\{nr}[\\{target}(\|e)])\?\|n*%
\\{nr}[\\{source}(\|e)]+\\{nr}[\\{target}(\|e)]:\|n*\\{nr}[\\{target}(\|e)]+%
\\{nr}[\\{source}(\|e)]);{}$\2\6
${}\|G.\\{sort\_edges}(\\{cost});{}$\7
${}\&{list}\langle\&{edge}\rangle{}$ \|L${}\K\|G.\\{all\_edges}(\,);{}$\6
${}\&{list}\langle\&{edge}\rangle{}$ \\{n\_edges};\7
\&{while} ${}(\R\|L.\\{empty}(\,)){}$\5
${}\{{}$\1\6
${}\|e\K\|L.\\{pop}(\,);{}$\6
\&{if} ${}(\R\|L.\\{empty}(\,)\W\\{source}(\|e)\E\\{target}(\|L.\\{head}(\,))\W%
\\{target}(\|e)\E\\{source}(\|L.\\{head}(\,))){}$\1\5
${}\|L.\\{pop}(\,);{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{n\_edges}.\\{append}(\|G.\\{new\_edge}(\\{target}(\|e),\39\\{source}(%
\|e)));{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\\{Make\_biconnected\_graph}(\|G);\6
${}\\{PLANAR}(\|G,\39\\{true});{}$\7
${}\&{node\_array}\langle\&{int}\rangle{}$ \\{xcoord}(\|G)${},{}$ \\{ycoord}(%
\|G);\7
${}\\{STRAIGHT\_LINE\_EMBEDDING}(\|G,\39\\{xcoord},\39\\{ycoord});{}$\7
\&{float} \|f${}\K\T{900.0}/(\T{2}*\|G.\\{number\_of\_nodes}(\,));{}$\7
\&{forall\_nodes} ${}(\|v,\39\|G){}$\1\5
${}\|G[\|v]\K\&{point}(\|f*\\{xcoord}[\|v]+\T{30},\39\T{2}*\|f*\\{ycoord}[\|v]+%
\T{30});{}$\2\6
\&{forall} ${}(\|e,\39\\{n\_edges}){}$\1\5
${}\|G.\\{del\_edge}(\|e);{}$\2\6
${}\|W.\\{clear}(\,);{}$\6
\&{if} ${}(\\{inp}\E\T{0}){}$\1\5
${}\\{draw\_graph}(\|G,\39\|W,\39\\{true}){}$;\SHC{ with node numbering }\2\6
\&{else}\1\5
${}\\{draw\_graph}(\|G,\39\|W);{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\|W.\\{message}(\.{"Graph\ is\ not\ planar}\)\.{.\ I\ compute\ the\ Kura}\)%
\.{towski\ subgraph\ ..."});{}$\7
${}\&{list}\langle\&{edge}\rangle{}$ \|L;\7
${}\\{PLANAR}(\|G,\39\|L,\39\\{false});{}$\7
${}\&{node\_array}\langle\&{int}\rangle{}$ ${}\\{deg}(\|G,\39\T{0});{}$\6
\&{int} \\{lw}${}\K\|W.\\{set\_line\_width}(\T{3});{}$\6
\&{edge} \|e;\7
\&{forall} ${}(\|e,\39\|L){}$\5
${}\{{}$\1\6
\&{node} \|v${}\K\\{source}(\|e);{}$\6
\&{node} \|w${}\K\\{target}(\|e);{}$\7
${}\\{deg}[\|v]\PP;{}$\6
${}\\{deg}[\|w]\PP;{}$\6
${}\|W.\\{draw\_edge}(\|G[\|v],\39\|G[\|w]);{}$\6
\4${}\}{}$\2\7
\&{int} \|i${}\K\T{1}{}$;\C{ We highlight the Kuratowski subgraph. Nodes with
degree are drawn black. The nodes with larger degree are shown green and
numbered from 1 to 6 }\7
\&{forall\_nodes} ${}(\|v,\39\|G){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{deg}[\|v]\E\T{2}){}$\1\5
${}\|W.\\{draw\_filled\_node}(\|G[\|v],\39\\{black});{}$\2\6
\&{if} ${}(\\{deg}[\|v]>\T{2}){}$\5
${}\{{}$\1\6
\&{int} \\{nw}${}\K\|W.\\{set\_node\_width}(\T{10});{}$\7
${}\|W.\\{draw\_int\_node}(\|G[\|v],\39\|i\PP,\39\\{green});{}$\6
${}\|W.\\{set\_node\_width}(\\{nw});{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
${}\|W.\\{set\_line\_width}(\\{lw});{}$\6
\4${}\}{}$\2\par
\U35.\fi

\M{41}We reset the graphics window.

\Y\B\4\X41:reset window\X${}\E{}$\6
$\|W.\\{set\_show\_coordinates}(\\{false});{}$\6
${}\|W.\\{set\_frame\_label}(\.{"click\ any\ button\ to}\)\.{\ continue"});{}$\6
${}\|W.\\{read\_mouse}(\,){}$;\SHC{ wait for a click }\6
${}\|W.\\{reset\_frame\_label}(\,);{}$\6
${}\|W.\\{set\_show\_coordinates}(\\{true}){}$;\par
\U35.\fi

\N{1}{42}Some Theory.    \label{reprint}

We give the theory underlying the planarity test as described in
\cite[section IV.10]{Me:book}.
%Our next ...

\bibliography{/KM/usr/mehlhorn/tex/my}
\bibliographystyle{alpha}
\end{document}
\fi


\inx
\fin
\con
